1.今日のプログラミング
前回は、セレクトソートをやりました。
が、順番を間違えたため関係はあまりないです。
今回はインサートソートに基づいて作られたシェルソートについてやっていこうと思います。
環境
VisualStadio 2022
C#
2.シェルソート
シェルソートとは、一定間隔でグループ分けをして、そのグループ内で並び替えを行い、間隔を小さくしながらまた並び替えをする、ソートアルゴリズムの一つです。
ここでいう並び替えはインサートソートの事です。
ゆえに、インサートソートをもとにして作られたソートアルゴリズムなのです。
ただし、弱点があります。
それは、すごくぐちゃぐちゃなソートはあまり得意じゃないところです。
シェルソートは、「概ねソート済みの配列に対しては高速」という性能を最大限引き出すアルゴリズムなので、とても不安定な内部ソートです。
—内部的な動き—
配列[4,6,2,5,1,3]について考えるとします。
まず、配列をABCの3パターンのグループに分けます。
A、B、C、A、B、C
|| || || || || ||
4、6、2、5、 1、 3
そして、同じグループ同士で並び替えをします。
この場合は、
A : 4 ＜ 5 noSwap
B : 6 ＞ 1 Swap
C : 2 ＜ 3 noSwap
☟結果
[4、1、2、5、6、3]
次は、配列をABの2パターンで分けます。
A、B、A、B、A、B
|| || || || || ||
4、1、2、5、 6、 3
そして同じグループ同士で分けます。
A : 2、4、6
B : 1、3、5
☟結果
[2、1、4、3、6、5]
最後に並び替えて
[1、2、3、4、5、6]
ソート完了。
やってみましょう。
namespace ShellSort
{
internal class Program
{
static void Main(string[] args)
{
int[] number = {5,7,6,3,9,8,2,1,4,0};
Shell(number);
for(var i = 0; i < number.Length; i++)
{
Console.WriteLine(number[i]);
}
while (true) ;
}
public static void Shell(int[] array)
{
//グループ分け（array.Length / 2でグループの数を決めてる。）
//（間隔を徐々に狭くしてるのは、group = group / 2）
for(var group = array.Length / 2; group > 0; group = group / 2)
{
for(var i = group; i < array.Length; i++)
{
var j = i;
while(j - group >= 0 && array[j] < array[j - group])
{
Swap(array, j, j - group);
j = j - group;
}
}
}
}
public static void Swap(int[] array , int a, int b)
{
array[a] = array[a] + array[b];
array[b] = array[a] - array[b];
array[a] = array[a] - array[b];
}
}
}
実行結果
0
1
2
3
4
5
6
7
8
9
ここら辺から難しくなってきましたね。
シェルソートのメリットは、最良の場合の計算時間はインサートソートと変わらないのですが、最悪の場合の計算時間がシェルのほうが早い。というとこが良いところでしょう。
それと、インサートソート（挿入ソート）を触れてからのほうが書きやすかったかもしれないです。
なので次回はインサートソートについてやりましょう。
ちょっとした予習をした感じでみてください。
まとめ
やはり、インサートソートの弱点がほぼ無くなったシェルソートはいいですね。
どんどん早い方を使っていきましょう！
ちなみにシェルソートの「シェル」はドナルド・シェルさんというコンピュータ科学者の名前が由来らしいヨ。
参考にするといいサイト
https://medium-company.com/シェルソート/
https://www.codereading.com/algo_and_ds/algo/shell_sort.html
https://programming-place.net/ppp/contents/algorithm/sort/005.html