データをソートする処理をよく使いますが、どのようなアルゴリズムになっているのでしょうか？ また一番速い方法はどれでしょうか？
Contents
挿入ソート
挿入ソートは、データ列を整列済みとそうでないものに分け、未整列な部分からデータを1つ取り出し、整列済み部分の適切な位置に挿入することを繰り返す手法です。未整列な部分がなくなるまで処理を繰り返すと、ソートされた配列にすることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Program { static void InsertionSort(int []vs) { int n = vs.Length; for (int i = 0; i < n; i++) { // vs[i] を、整列済みの vs[0] ～ vs[i-1] の適切な位置に挿入する // vs[i] の値をバックアップしておく int bk = vs[i]; // vs[i] の適切な挿入位置を表す変数 x を用意 int x = i - 1; // vs[i] の適切な挿入位置が見つかるまで、vs[i] より大きい要素を1つずつ後ろにずらしていく while (x >= 0 && vs[x] > bk) { vs[x + 1] = vs[x]; x--; } vs[x + 1] = bk; // vs[0] ～ vs[i] が整列済みになった } } } |
選択ソート
選択ソートは、挿入ソートと同じように整列済み部分とそうでない部分にわけるところまでは同じですが、未整列な部分から最小値を取り出し（昇順の場合）、整列済み部分の末尾に付け加えることを繰り返す手法です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class Program { static void SelectionSort(int[] vs) { int n = vs.Length; for (int i = 0; i < n - 1; i++) { // vs[i] ～ vs[n-1] の最小値を見つけ、vs[i]と交換する // つまり整列済みとなっている vs[0] ～ vs[i-1] の末尾に、vs[i] ～ vs[n-1] の最小値を付け加える // vs[i] ～ vs[n-1] の最小値の位置を保存する変数 minIndex を用意 // 暫定的に vs[i] を最小値とする int minIndex = i; // 最小値を探す for (int x = i + 1; x < n; x++) { if (vs[x] < vs[minIndex]) minIndex = x; } // vs[i] と vs[min_index]を交換 int c = vs[i]; vs[i] = vs[minIndex]; vs[minIndex] = c; // vs[0] ～ vs[i] が整列済みになった Console.WriteLine(String.Join(" ", vs)); } } } |
バブルソート
バブルソートは、データ列の隣り合う要素を比較し交換することを繰り返すことによりデータ列をソートする手法です。ソートの過程でデータが移動する様子が、水中で泡が浮かんでいくように見えることからこのような名前になっています。前二者と比べるとコードが短いです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class Program { static void BubbleSort(int[] vs) { int n = vs.Length; for (int i = 0; i < n - 1; i++) { for (int x = n - 1; x >= i + 1; x--) { if (vs[x - 1] > vs[x]) { int c = vs[x - 1]; vs[x - 1] = vs[x]; vs[x] = c; } } } } } |
シェルソート
シェルソートは、挿入ソートを改良したアルゴリズムです。挿入ソートが整列済みのデータ列に強いことを利用しています。
シェルソートは、データ列において一定の間隔 h だけ離れた要素からなる部分列を対象に、挿入ソートをhを小さくしながら繰り返します。h は適当に大きな値から始め、段階的に小さくしていき、最終的に 1 にします。
シェルソートの計算量は間隔列 H に強く依存します。シェルソートの計算量解析を正確に行うことは難しく未解決なのですが、いくつかの有名な間隔列に対しては計算量解析が行われています。例えば漸化式 Hi = 3 * H(i+1) + 1を満たす整数列、1, 4, 13, 40, 121, 364を逆にしたものを間隔列とした場合のシェルソートは平均計算量が O(n^{1.25}) になることが知られています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Program { static void Main() { // 配列が短いと挿入ソートとあまり変わらない int[] vs = { 11, 9, 12, 8, 13, 7, 14, 6, 15, 1, 19, 2, 18, 3, 17, 4, 16, 5, 10,}; int[] hs = {13, 4, 1, }; ShellSort(vs, vs.Length, hs); Console.WriteLine(String.Join(" ", vs)); // 結果を表示 } static void ShellSort(int[] vs, int n, int[] hs) { foreach (int h in hs) { InsertionSort(vs, n, h); } } static void InsertionSort(int[] vs, int n, int h) { for (int i = 0; i < n; i++) { // vs[i] を、整列済みの vs[i-a*h], ..., vs[i-2*h], vs[i-h] の適切な位置に挿入する // vs[i] の値をバックアップしておく int bk = vs[i]; // vs[i] の適切な挿入位置を表す変数 j を用意 int x = i - h; // vs[i] の適切な挿入位置が見つかるまで、vs[i] より大きい要素を後ろにずらしていく while (x >= 0 && vs[x] > bk) { vs[x + h] = vs[x]; x -= h; } // vs[i] を挿入 vs[x + h] = bk; } } } |
マージソート
マージソートは、データ列を二分し、それぞれをソートした後それらを統合することを繰り返すソートアルゴリズムです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
class Program { static void Main() { int[] vs = { 7, 6, 10, 2, 5, 4, 8, 3, 9, 1, }; MergeSort(vs, 0, vs.Length); Console.WriteLine(String.Join(" ", vs)); // 結果を表示 } static void MergeSort(int[] vs, int left, int right) { if (left + 1 < right) { int mid = (left + right) / 2; MergeSort(vs, left, mid); MergeSort(vs, mid, right); Merge(vs, left, mid, right); } } static void Merge(int[] vs, int left, int mid, int right) { // 2つの部分データ列のサイズ int countL = mid - left + 1; int countR = right - mid + 1; // 部分データ列をコピー int[] lefts = new int[countL]; for (int i = 0; i < countL-1; i++) lefts[i] = vs[left + i]; int[] rights = new int[countR]; for (int i = 0; i < countR-1; i++) rights[i] = vs[mid + i]; // 番兵 lefts[countL-1] = int.MaxValue; rights[countR-1] = int.MaxValue; // 2つの部分データ列をマージして A[left] ~ A[right-1] に書き込む int indexL = 0; int indexR = 0; for (int i = left; i < right; i++) { if (lefts[indexL] < rights[indexR]) { vs[i] = lefts[indexL]; indexL++; } else { vs[i] = rights[indexR]; indexR++; } } } } |
クイックソート
クイックソートは、ピボットと呼ばれる値を1つ選び、それを基準としてデータ列をピボット未満の要素とピボット以上の要素のふたつにわける処理を再帰的に行うアルゴリズムです。
ピボットの選び方にはいくつか方法があります。
データ列の先頭をとる
データ列の末尾をとる
データ列からランダムにとる
データ列からランダムに2つとり、その中央値をとる
ピボットを選択したら、データ列の先頭からデータを1つずつ確認していき、ピボット未満のデータをデータ列の先頭に集め、ピボットをそれより左側がピボット未満、右側がピボット以上となるように移動します。ここでデータ列を二つにわけ、分割された2つのデータ列に対して再び同じ操作を繰り返します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
class Program { static void Main() { int[] vs = { 7, 6, 10, 2, 5, 4, 8, 3, 9, 1, }; QuickSort(vs, 0, vs.Length); Console.WriteLine(String.Join(" ", vs)); } static void QuickSort(int[] vs, int left, int right) { // ソートする範囲の長さが1以下の場合は何もしない if (left + 1 >= right) return; // データ列の末尾 vs[right-1] をピボットとする int pivot = vs[right - 1]; // ピボット未満のデータを挿入する位置を保持する変数を用意 int curIindex = left; int tmp; // 数値交換用 for (int i = left; i < right - 1; i++) { if (vs[i] < pivot) { { // 入れ替える tmp = vs[curIindex]; vs[curIindex] = vs[i]; vs[i] = tmp; } curIindex++; } } // ピボットを vs[curIindex] へ移動し、データ列を分割する { // 入れ替える tmp = vs[curIindex]; vs[curIindex] = vs[right - 1]; vs[right - 1] = tmp; } // 分割されたデータ列に対して再帰的にクイックソートを行う QuickSort(vs, left, curIindex); QuickSort(vs, curIindex + 1, right); } } |
処理が高速なのはどれ？
実際にどれくらい時間がかかるのか計測してみることにします。
クイックソートとマージソートはすぐに終わりますが、選択ソートと挿入ソートとバブルソートは時間がかかります。
以下のようなコードを書いて実験してみることにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Program { static void Main() { int count = 100 * 10000; int[] vs = new int[count]; Console.WriteLine("乱数を生成中"); Random random = new Random(); for (int i = 0; i < count; i++) { vs[i] = random.Next(count); } int[] vs1 = (int[])vs.Clone(); int[] vs2 = (int[])vs.Clone(); System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); Console.WriteLine("クイックソート開始"); sw.Reset(); sw.Start(); QuickSort(vs1, 0, vs1.Length); sw.Stop(); Console.WriteLine("クイックソート：{0} ms", sw.ElapsedMilliseconds); Console.WriteLine("マージソート開始"); sw.Reset(); sw.Start(); MergeSort(vs2, 0, vs2.Length); sw.Stop(); Console.WriteLine("マージソート：{0} ms", sw.ElapsedMilliseconds); } } |
クイックソートとマージソートのほうが速いです。
では挿入ソートと選択ソート、バブルソートの場合はどうでしょうか？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
class Program { static void Main() { int count = 10000; int[] vs = new int[count]; Console.WriteLine("乱数を生成中"); Random random = new Random(); for (int i = 0; i < count; i++) { vs[i] = random.Next(count); } int[] vs1 = (int[])vs.Clone(); int[] vs2 = (int[])vs.Clone(); int[] vs3 = (int[])vs.Clone(); System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); Console.WriteLine("挿入ソート開始"); sw.Reset(); sw.Start(); InsertionSort(vs1); sw.Stop(); Console.WriteLine("挿入ソート：{0} ms", sw.ElapsedMilliseconds); Console.WriteLine("選択ソート開始"); sw.Reset(); sw.Start(); SelectionSort(vs2); sw.Stop(); Console.WriteLine("選択ソート：{0} ms", sw.ElapsedMilliseconds); Console.WriteLine("バブルソート開始"); sw.Reset(); sw.Start(); BubbleSort(vs3); sw.Stop(); Console.WriteLine("バブルソート：{0} ms", sw.ElapsedMilliseconds); } } |
速い順に挿入ソート、選択ソート、バブルソートです。
シェルソートと挿入ソートの比較
次にシェルソートと挿入ソートを比較してみることにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
class Program { static void Main() { int count = 10000; int[] vs = new int[count]; Console.WriteLine("乱数を生成中"); Random random = new Random(); for (int i = 0; i < count; i++) { vs[i] = random.Next(count); } int[] vs1 = (int[])vs.Clone(); int[] vs2 = (int[])vs.Clone(); System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); Console.WriteLine("シェルソート開始"); sw.Reset(); sw.Start(); List<int> hs = new List<int>(); { hs.Add(1); int preValue = 1; while (true) { preValue = preValue * 3 + 1; if (vs1.Length < preValue * 3) break; hs.Add(preValue); } hs.Reverse(); } ShellSort(vs1, vs1.Length, hs.ToArray()); sw.Stop(); Console.WriteLine("シェルソート：{0} ms", sw.ElapsedMilliseconds); Console.WriteLine("挿入ソート開始"); sw.Reset(); sw.Start(); InsertionSort(vs2); sw.Stop(); Console.WriteLine("挿入ソート：{0} ms", sw.ElapsedMilliseconds); } } |
シェルソートのほうが圧倒的に速いです。マージソートとも比較してみましたが、マージソートのほうが速いです。
クイックソートが一番速い？
いまのところクイックソートが一番速いですが、いつも使っているLinq.OrderByメソッドをつかったソートとではどちらが速いのでしょうか？ int型配列で試してみましたが、クイックソートのほうが約1.6倍速いことがわかりました。
またint型配列をソートするのであればArray.Sort()を使うのが一番速いです。クイックソートと比べると3倍以上違います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Program { static void Main() { int[] vs1 = (int[])vs.Clone(); int[] vs2 = (int[])vs.Clone(); int[] vs3 = (int[])vs.Clone(); _ = vs1.OrderBy(x => x).ToArray(); QuickSort(vs2, 0, vs2.Length); Array.Sort(vs3); // これが一番速い } } |
