一日一プロ
シェルソート
あらかじめソートしておき、挿入ソートでの計算回数を少なくする。
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