一日一プロ

シェルソート

あらかじめソートしておき、挿入ソートでの計算回数を少なくする。

using System;
using System.Collections.Generic;

namespace ShellSort
{
	class MainClass
	{
		public static void Main (string[] args)
		{
			int mode = 0;
			int gMax = 0;

			Console.WriteLine ("0:Settiing,1:Random");
			mode = int.Parse (Console.ReadLine ());

			Console.WriteLine ("LinstCount:");
			int N = int.Parse (Console.ReadLine ());

			List<int> data = new List<int> ();
			if (mode == 0) {
				Console.WriteLine ("List:");
				for (int i = 0; i < N; i++) {
					data.Add (int.Parse (Console.ReadLine ()));
				}
			} else {
				Random rnd = new System.Random();
				for (int i = 0; i < N; i++) {
					data.Add (rnd.Next (100));
				}
			}
				
			Console.WriteLine ("gMax:");
			gMax = int.Parse (Console.ReadLine ());


			for(int g_num=1; g_num <= gMax; g_num++){
				List<int> listG = new List<int> ();
				calcG (listG, g_num);

				List<int> soreteList = new List<int> (data);

				int cnt = 0;
				for (int i = g_num - 1; i >= 0; i--) {
					cnt += insertSort (soreteList, listG [i]);
					printList (soreteList);
				}
				Console.WriteLine ("g:{0} Count:{1} \n", g_num, cnt);
			}
		}

		public static int insertSort(List<int> data, int g)
		{
			int cnt = 0;
			for (int i = g; i < data.Count; i++) {
				int v = data [i];
				int j = i - g;
				while (j >= 0 && data [j] > v) {
					data [j + g] = data[j];
					j -= g;
					cnt++;
				}
				data [j + g] = v;
			}

			return cnt;
		}

		public static void printList(List<int> data){
			for (int i = 0; i < data.Count; i++) {
				Console.Write ("{0},", data [i]);
			}
			Console.Write ("\n");
		}

		public static void calcG(List<int> gList, int num){
			int tmp = 1;
			//1,4,13,40,121..
			for (int i = 0; i < num; i++) {
				gList.Add (tmp);
				tmp = 3 * tmp + 1;
			}
		}
	}
}

実行結果

0:Settiing,1:Random
1
LinstCount:
50
gMax:
5
0,5,7,10,12,17,22,25,27,28,29,31,32,33,35,38,39,40,42,43,44,49,54,54,55,56,56,57,60,62,64,65,65,69,70,72,74,75,77,78,81,81,81,81,82,84,89,89,93,97,
g:1 Count:531

17,7,5,0,29,22,32,10,40,25,33,12,43,27,54,28,49,31,55,35,54,38,57,39,56,42,64,44,56,60,65,62,78,70,65,69,81,72,75,77,81,74,93,81,82,81,97,89,84,89,
0,5,7,10,12,17,22,25,27,28,29,31,32,33,35,38,39,40,42,43,44,49,54,54,55,56,56,57,60,62,64,65,65,69,70,72,74,75,77,78,81,81,81,81,82,84,89,89,93,97,
g:2 Count:228

5,39,60,0,28,22,12,49,7,35,10,25,54,17,75,64,54,31,29,32,55,40,38,33,44,56,27,81,69,65,57,77,42,62,65,43,78,81,74,81,89,84,70,82,93,56,72,89,97,81,
5,17,10,0,7,22,12,25,28,31,27,32,42,35,29,33,44,39,38,43,54,40,57,49,54,56,60,64,55,56,65,77,69,62,70,81,78,65,72,81,89,81,74,82,93,81,75,89,97,84,
0,5,7,10,12,17,22,25,27,28,29,31,32,33,35,38,39,40,42,43,44,49,54,54,55,56,56,57,60,62,64,65,65,69,70,72,74,75,77,78,81,81,81,81,82,84,89,89,93,97,
g:3 Count:161

17,60,64,0,29,22,32,62,40,38,33,44,56,27,75,69,54,31,93,12,49,7,97,10,81,74,5,39,84,70,57,77,56,72,65,35,78,25,54,81,81,89,65,28,82,42,55,89,43,81,
5,39,64,0,28,22,12,49,7,35,10,25,54,17,60,69,54,29,77,32,55,40,38,33,44,56,27,75,84,65,31,82,42,62,65,43,78,81,74,81,81,89,70,57,93,56,72,89,97,81,
5,17,10,0,7,22,12,25,28,29,27,32,42,35,31,33,44,39,38,43,54,40,60,49,54,56,64,57,55,56,65,69,78,62,70,75,81,65,72,81,84,81,74,82,93,81,77,89,97,89,
0,5,7,10,12,17,22,25,27,28,29,31,32,33,35,38,39,40,42,43,44,49,54,54,55,56,56,57,60,62,64,65,65,69,70,72,74,75,77,78,81,81,81,81,82,84,89,89,93,97,
g:4 Count:160

17,89,64,0,82,22,32,62,40,38,33,44,56,27,75,69,54,31,93,12,49,7,97,10,81,74,5,39,84,70,57,77,56,72,65,35,78,25,54,81,81,60,65,28,29,42,55,89,43,81,
17,60,64,0,29,22,32,62,40,38,33,44,56,27,75,69,54,31,93,12,49,7,97,10,81,74,5,39,84,70,57,77,56,72,65,35,78,25,54,81,81,89,65,28,82,42,55,89,43,81,
5,39,64,0,28,22,12,49,7,35,10,25,54,17,60,69,54,29,77,32,55,40,38,33,44,56,27,75,84,65,31,82,42,62,65,43,78,81,74,81,81,89,70,57,93,56,72,89,97,81,
5,17,10,0,7,22,12,25,28,29,27,32,42,35,31,33,44,39,38,43,54,40,60,49,54,56,64,57,55,56,65,69,78,62,70,75,81,65,72,81,84,81,74,82,93,81,77,89,97,89,
0,5,7,10,12,17,22,25,27,28,29,31,32,33,35,38,39,40,42,43,44,49,54,54,55,56,56,57,60,62,64,65,65,69,70,72,74,75,77,78,81,81,81,81,82,84,89,89,93,97,
g:5 Count:160