シェルソートをわかりやすくまとめる

シェルソートについて、わかりやすくまとめたいと思います。

シェルソートとは

一定間隔(g)ごとに挿入ソートを行うことをシェルソートといいます。 最後に必ず、通常の挿入ソートを行いますが、
この時に、あらかた整列されていることが期待されます。

この一定間隔gの決め方ですが

g = 1,4,13,40,121・・・

つまりは、
$g_{n+1} = 3g_{n} + 1$の数列を用いると、
計算量が$O(N^{1.25})$になるようです。

また、上記のgを適応すると、2のべき乗の値($2^p = 1,2,4,...$)の場合は、ソート対象となる要素が少なくなるため、
効率化は見込めないようです。

シェルソートの工程を図解する

実際にシェルソートが行われる工程を図解してみます。

数列{4,8,9,1,10,6,2,5,3,7}に対して、 g{4,3,1}として、シェルソートをかけてみます。

ここで、選択対象数字を赤で、整列済みの数字を緑で表現したいと思います。

1.間隔を4に空けて挿入ソートをかけます。

4,8,9,1,10,6,2,5,3,7
3,8,9,1,4,6,2,5,10,7

3,8,9,1,4,6,2,5,10,7
3,6,9,1,4,7,2,5,10,8

3,6,9,1,4,7,2,5,10,8
3,6,2,1,4,7,9,5,10,8

3,6,2,1,4,7,9,5,10,8
3,6,2,1,4,7,9,5,10,8

2.間隔を3に空けて挿入ソートをかけます。

3,6,2,1,4,7,9,5,10,8
1,6,2,3,4,7,8,5,10,9

1,6,2,3,4,7,8,5,10,9
1,4,2,3,5,7,8,6,10,9

1,4,2,3,5,7,8,6,10,9
1,4,2,3,5,7,8,6,10,9

3.最後に間隔1(通常)に空けて挿入ソートをかけます。

1,4,2,3,5,7,8,6,10,9
1,2,3,4,5,6,7,8,9,10

安定ソートとはどういう概念なのか

安定ソートに関して、まとめます。

安定ソートとそうでないソートの例

wikipediaの例を参考にして、まとめます。
学生番号とテストの合計点が書かれたデータがあるとします。

学生番号	テスト合計点
1	419
2	366
3	402
4	453
5	419
6	402

このデータは、学生番号順に並んでいます。
これをテスト合計点順にバブルソートと選択ソートを使って並び替えてみたいと思います。

テスト合計点順にバブルソートで並び替えた場合

バブルソートで並び替えた場合以下のようになります。 計算過程は省略します。

学生番号	テスト合計点
2	366
3	402
6	402
1	419
5	419
4	453

同じ合計点の例に着目すると、学生番号順にならんでいることがわかります。
この性質のことを安定ソートといいます。
バブルソートは同じ点数の際は入れ替えないため、学生番号の順序も変わらないんですね。

テスト合計点順に選択ソートで並び替えた場合

テスト合計順に選択ソートを使って、並び替えてみたいと思います。

1.まずデータの中から最小得点のデータを探し出します。

学生番号2、点数366が最小なので、左端のデータと交換します。

　　　　

学生番号	テスト合計点
2	366
1	419
3	402
4	453
5	419
6	402

2.
一番目が決まったので、2番目から最小値を探索していきます。
最小値は402学生番号は3のデータになります。

　　　　

学生番号	テスト合計点
2	366
3	402
1	419
4	453
5	419
6	402

3.
3番目から最小値を探します。
最小値は402学生番号は6のデータになります。

　　　　

学生番号	テスト合計点
2	366
3	402
6	402
4	453
5	419
1	419

この時点で、419点において、学生番号が入れ替わってしまいました。

計算過程は省略しますが、学生番号が入れ替わったまま、得点順に並び替えられるのは、
選択ソートの性質上明らかですね。

このように元の順序が変わってしまうソートを不安定ソートといいます。

選択ソートについて、わかりやすくまとめる

選択ソートアルゴリズムについて、わかりやすくまとめたいと思います。

選択ソートは、数列の中から最大または最小の数値を探しだして、その数値と左端の数値を交換することで、 ソートしていくアルゴリズムです。

では、例題で確認してみます。

選択ソートの例題

以下の数列を選択ソートを使ってを昇順に並べて変えてみたいと思います。
昇順に並び替えるので、最小値を選択して数列の左端から並び替えることにします。

5,4,8,7,9

また、対象となっている文字を赤で、ソート済みの数値を緑で表示して、わかりやすくしてみます。

一回目の選択

数列の左端から右端まで最小の値を探していきます。

5,4,8,7,9

左端の値5を最小の値として保存します。
次に右を探索していき、5よりも最小の値があれば、最小の値を更新します。

5,4,8,7,9

5 > 4なので、最小の値が4に変わりました。
次に、8,7,9をチェックしていきますが、最小値は4のままなので、
4と5を交換します。

4,5,8,7,9

これで、最小値がきまり、左端の値が決定しました。
次に、2番目の値つまり5からまた、最小値を探して交換を繰り返していきます。

これが選択ソートになります。

選択ソートの計算量

データの総数をNとすると、
未ソート部分の最小値を探し出すのに、N - 1回、N - 2回, N - 3回、...、1の比較演算を行います。

よって、合計の比較演算回数は、常に(N^2 - N) / 2になるので、 N^2に比例するため、O(N^2)のアルゴリズムになります。