【Java アルゴリズム修行⑬】シェルソート

シェルソートとは

前回まででバブル、単純選択、挿入ソートと基礎的なソートを学習しましたが、
O(nの二乗)という速度のため、あまり速いソートとは言えないそうです。
今回からは、速さが改善されたシェルソート、クイックソート、マージソート、ヒープソートたちを学んでいこうと思います！

シェルソートというと、

単純挿入ソートの長所を活かしつつ、その短所を補うことで、高速にソートを行うアルゴリズム

とされており、単純挿入ソートをグレードアップした形のものらしいです。
単純挿入ソートというと、先頭+1の要素を一時変数とし保存し、それより小さい値を見つける位置まで代入を繰り返し、
適切な位置に値を挿入するというものでした。

例えば、{1,2,3,4,5,0,6}という数列があるとすると以下のようになります。
※実際の挿入ソートコードはこちらを確認してください！

■ i = 1から始まる
tmp変数には a[1]の2が代入される
もし j > 0 かつ、a[1-1] > 2　だったら代入操作を行うが、
この時点で既に a[0] の1よりも 2の方が大きいので代入操作は行わずにfor文を抜ける

a[1] = 2でそのまま変わらない → {1,2,3,4,5,0,6}

■ i =2 なので
tmp変数にはa[2]の3が代入される
もし j > 0 かつ　a[2-1] > 3 だったら代入操作を行うが、
この時点で既にa[1]の2の方が小さいので、代入操作は行わずにfor文を抜ける
a[2] =3でそのまま変わらない → {1,2,3,4,5,0,6}

■ i = 3 なので
tmp変数にはa[3]の4が代入される
もし j > 0 かつ　a[3-1] > 4 だったら代入操作を行うが、
この時点で既にa[2]の3の方が小さいので、代入操作は行わずにfor文を抜ける
a[3] = 4なので変わらない → {1,2,3,4,5,0,6}

■ i = 4 なので
tmp変数にはa[4]の5が代入される
もし j > 0 かつ　a[4-1] > 5 だったら代入操作を行うが、
この時点で既にa[3]の4の方が小さいので、代入操作は行わずにfor文を抜ける
a[4] = 5なので変わらない →{1,2,3,4,5,0,6}

■ i = 5 なので
tmp変数にはa[5]の0が代入される
もし j > 0 かつ　a[5-1] > 0 だったら代入操作を行うので、
a[4] の5の方が大きいため、代入操作を行い、
a[5] = a[4]の5が代入され、 {1,2,3,4,5,5,6}

もし j > 0 かつ　a[4-1] > 0 だったら代入操作を行うので
a[3] の4の方が大きいため、代入操作を行い、
a[4] に a[3]の4を代入して {1,2,3,4,4,5,6}

もし j > 0 かつ　a[3-1] > 0 だったら代入操作を行うので
a[2] の3の方が大きいため、代入操作を行い、
a[3] に a[2]の3を代入して {1,2,3,3,4,5,6}

もし j > 0 かつ　a[2-1] > 0 だったら代入操作を行うが、
a[1] の2の方が大きいため、代入操作を行い、
a[2]にa[1]の2を代入して {1,2,2,3,4,5,6}

もし j > 0 かつ　a[1-1] > 0 だったら代入操作を行うが、
a[0] の1の方が大きいため、代入操作を行い、
a[1]にa[0]の1を代入して {1,1,2,3,4,5,6}

この時点で j > 0 はfalseなので for文を抜けて
a[0]に 0が代入され、{0,1,2,3,4,5,6}として0が先頭に持ってこられる

という流れになります。

とは言え、0を前に持ってくるだけのソートに6回もの代入はあまり効率がいいとは言えません。

ここから、単純挿入ソートが以下のような特徴を持っていることが分かります。


① ソート済あるいは、それに近い状態（i = 1 ~4まで）では高速で処理できる
② 挿入先が遠く離れている場合は、一つずつ比較、代入を行うので回数が増える



①は長所・②は短所として、この①を活かしつつ、②を補うのがシェルソート

君ということになるようです。。
最初に等間隔の要素をグループ化して、グループごとにソートを行い
そのグループを縮小していきながらソートを繰り返すことで、移動回数を減らそうというアイデアみたいですね！

試しに、{4,3,5,7,1,8,6,2}という数列で図にしながら考えてみましょう。

まずは4間隔で取り出した4つのグループに分けると、
{4,1}{3,8}{5,6}{7,2}となります

その後、各グループをそれぞれソートすると、{1,4}{3,8}{5,6}{2,7}という順番になり、
数列に戻すと {1,3,5,2,4,8,6,7}として、
この時点でソートは完了していないものの、ソート済の状態に近付いていくのが分かります。

次に、2個間隔で取り出した{1,5,4,6}{3,2,8,7}の2つのグループに分けます。

そのまま各グループをソートすると、{1,4,5,6}{2,3,7,8}とソートされるので
結果的には{1,2,4,3,5,7,6,8}という並びになります。

得られた配列はさらにソート済の状態に近づいたので、最後に1個感覚で取り出した並び、
つまり配列全体となるので、そのままソートしてみましょう。

無事に{1,2,3,4,5,6,7,8}という並びになり、シェルソートが完了
しました。

{4,3,5,7,1,8,6,2}という数列から、

2個の要素に対して、4-ソートを行う× 4グループ →4回 {4,1}{3,8}{5,6}{7,2}
4個の要素に対して、2-ソートを行う× 2グループ →2回 {1,5,4,6}{3,2,8,7}
1個の要素に対して、1-ソートを行う × 1グループ →1回 {1,2,4,3,5,7,6,8}


こうして整理してみると、計7回のソートで完了させることができます。

単純挿入ソートを頭からいきなり適用せずに、
4-ソートや、2-ソートによる地ならしを行い
、ソート済に近い状態にしておき、
それから単純挿入ソートを最後に行うことで、ソートを完了させる

ソートの回数は増えても、
全体としての要素の移動回数は少なくなることが期待できそうです。

ここまで流れが分かってきたので、早速コードに落とし込んでみましょう。

コードで再現してみる

    static void shellSort(int[] a, int n) {
        //要素数/2でグループ分けする等間隔を求める
        for (int h = n / 2; h > 0; h /= 2) {
              for (int i = h; i < n; i++) {
                int j;
                int tmp = a[i];
                //等間隔を持った値同士の大小を比較し、先頭寄の要素より小さければ交換を行う
                for (j = i - h; j >= 0 && a[j] > tmp; j -= h) {
                    a[j + h] = a[j];
                    }
                a[j + h] = tmp;
                }
            }
        }

（引数のaはソートしたい配列、nは要素数です）

単純挿入ソートを行う部分は同じですが、
着目要素と比較要素が、隣接した要素ではなく、h個だけ離れた要素に変わっています

。
そのhの初期値は h/2として求めており、
for文による繰り返しを行う度に2で割っているので、
4→2→1と半分の値になっていきます。

for (j = i - h; j >= 0 && a[j] > tmp; j -= h)部分で
間隔に応じた比較を行なっていますが、 i - h の初期値は常に0となるので、先頭要素から比較を行います。
j >= 0 && a[j] > tmpの条件式の初期段階では、
tmpの値はa[i(h)]となるため、先頭から、h個分離れた要素の値を比較しています。

もし先頭要素の方が大きければ、h個離れた部分に、先頭要素を代入し、（a[j + h] = a[j]）
その後の更新文でj -= hとして、jが-1になってしまった場合は
先頭を超えているので、次の要素へと比較対象を移していくということになります。

{8,1,4,2,7,6,3,5}という 8要素で考えてみましょう
まずは要素数の半分である 4間隔、2要素ずつに分けて繰り返し処理を行います

■ i = 4(h)なので、
tmpには a[4]である7が代入される
そこから、j = 4-4で0スタート　jが0以上かつ a[0]が7よりも大きければ交換を行うが
a[0]の8は大きいので、a[4]にa[0]の8を代入→ {8,1,4,2,8,6,3,5}
j - h は -4となるので、繰り返しは終了し、a[-4 + 4]に 7が代入→ {7,1,4,2,8,6,3,5}となる

■ i = 5なので、
tmpにはa[5]の6が代入される
そこから j = 5-4で1スタート、 jが0以上かつa[1]が6よりも大きければ交換を行うが、
a[1]の1は6よりも小さいので、繰り返し処理は施さず a[1+4]にそのまま6が代入→ {7,1,4,2,8,6,3,5}となる

■ i = 6なので、
tmpにはa[6]の3が代入される
そこから j = 6-4で2スタート、 jが0以上かつa[2]が3よりも大きければ交換を行うが、
a[2]の4の方が大きいので、a[6]にa[2]の4を代入　→ {7,1,4,2,8,6,4,5}
j - h は-2となるので、繰り返しは終了し [-2 + 4]に3を代入し {7,1,3,2,8,6,4,5}となる


■ i = 7なので、
tmpにはa[7]の5が代入される
そこから j = 7-4で3スタート jが0以上かつa[3]が5よりも大きければ交換を行うが
a[3]の2は小さいので、a[4+3]にそのまま5を代入して、{7,1,3,2,8,6,4,5}となる

ここでiは8となり i < 8 はfalseなので、次のループに入る。
4 / 2 で hは2となる　2間隔でソートを行う

■ i = 2(h)なので、
tmpには a[2]である3が代入される
そこから、j = 2-2で0スタート　jが0以上かつ a[0]が3よりも大きければ交換を行うが
a[0]の7は大きいので、a[2]にa[0]の7を代入 →{7,1,7,2,8,6,4,5}となる
j - h は -2となるので、繰り返しは終了し、a[-2 + 2]に 3が代入→{3,1,7,2,8,6,4,5}となる

■ i = 3なので、
tmpには a[3]である2が代入される
そこから、j = 3-2で1スタート　jが0以上かつ a[1]が2よりも大きければ交換を行うが
a[1]の1は小さいので、そのままa[3]に2が代入されて終了 →{3,1,7,2,8,6,4,5}となる

■ i = 4なので、
tmpには a[4]である8が代入される
そこから、j = 4-2で2スタート　jが0以上かつ a[2]が8よりも大きければ交換を行うが
a[2]の7は小さいので、そのままa[4]に8が代入されて終了→{3,1,7,2,8,6,4,5}となる

■ i = 5なので、
tmpには a[5]である6が代入される
そこから、j = 5-2で3スタート　jが0以上かつ a[3]が6よりも大きければ交換を行うが
a[3]の2は小さいので、そのままa[5]に6が代入されて終了→{3,1,7,2,8,6,4,5}となる

■ i = 6なので、
tmpには a[6]である4が代入される
そこから、j = 6-2で4スタート jが0以上かつ a[4]が4よりも大きければ交換を行うが
a[4]の8の方が大きいので、a[6]に8を代入する→{3,1,7,2,8,6,8,5}となる
j - h は 2なので、そのまま a[2] > tmpを確かめると、
a[2]の7の方が大きいので、a[4]に7を代入する→{3,1,7,2,7,6,8,5}となる
j-h は 0なので繰り返し処理を抜けて a[2]に4を代入する→ {3,1,4,2,7,6,8,5}となる


■ i = 7なので、
tmpには a[7]である5が代入される
そこから、j = 7-2で5スタート　jが0以上かつ a[5]が5よりも大きければ交換を行うが
a[5]の6の方が大きいので、a[7]に6を代入する→ {3,1,4,2,7,6,8,6}となる
j - h は 3なので、そのまま a[3] > tmpを確かめると
a[3]の2は5よりも小さいので、繰り返し処理を抜けて、a[5]に5を代入する→{3,1,4,2,7,5,8,6}となる

iはインクリメントされて8となり i < 8 はfalseなので、次のループに入り、
2/2で h は1となるので、ここからは1個ずつ挿入ソートを行うという流れですね。

最初は4個離れた値同士をソート（8要素あれば2要素ずつ）
次に2個離れた値同士をソート（8要素あれば4要素ずつ）
最後は1個離れ値同士なので、8要素をソート　ということで
要素を2で割った数だけ間隔を持った値同士だけでソートを繰り返し、ソート済の状態に近づけた上で、
最後に1要素ずつをソートすることによって、ソート回数を減らしています。

h/2で繰り返すなら、要素数が奇数だったらどうすんのよ！？って
一瞬自分でも思ったんですが、間隔ごとに分けた要素数が変わるだけで、やっていることは同じです。

試しに要素数5の{5,4,3,2,1}で考えてみましょう。

まずは　5 / 2 で2となるので、

■ i = 2(h)から始めます。
tmpには a[2]である3が代入される
そこから、j = 2-2で0スタート　jが0以上かつ a[0]が3よりも大きければ交換を行うが
a[0]の5は大きいので、a[2]にa[0]の5を代入→ {5,4,5,2,1}
j - h は -2となるためこのまま終了し、 a[-2 + 2]に3が代入され、 {3,4,5,2,1}となります

■ i = 3なので
tmpにはa[3]である2が代入される
そこから、 j = 3-2で1スタート jが0以上かつ a[1]が2よりも大きければ交換を行うが
a[1]の4は大きいので、a[3]にa[1]の4を代入→ {3,4,5,4,1}
j - h は -1となるためこのまま終了し、 a[-1 + 2]に2が代入され、 {3,2,5,4,1}となります

■ i = 4なので
tmpにはa[4]である1が代入される
そこから、 j = 4-2で2スタート jが0以上かつ a[2]が1よりも大きければ交換を行うが
a[2]の5は大きいので、a[4]にa[2]の5を代入→ {3,2,5,4,5}
j - h は 0となるためそのまま続けると

a[0]が1よりも大きければ交換を行うため
a[0]の3は大きいのでa[2]にa[0]の3を代入→{3,2,3,4,5}
j - h は -2となるため終了し、 a[-2 + 2]に1が代入され、{1,2,3,4,5}となります。

この時点でソートは完了してるため書きませんが、この次に ■ i = 1（h）も処理自体は行われます。
やっていることは変わらず2間隔ずつ、1,3,5番目と2,4番目でそれぞれ単純挿入ソートを行なっている感じですね！

学んだこと

• 単純挿入ソートは無駄なソートを行なっていることがあるため、遅い場合もある
• 要素数/2の間隔ごとの値の塊で単純挿入ソートを行うことで、 限りなくソート済に近い状態で1要素ずつソートさせることができる

間隔ごとに分けてソートしていく、というと複雑な分岐処理が必要なのでは、、と感じましたが
やっていることは先頭要素から、間隔の数分だけ離れた要素のみで単純挿入ソートを繰り返す
というシンプルなことなので、3重ループであっても、何のためのfor文でそれぞれ
どういった場合に繰り返し処理を行うのかという条件文の理解が大切なことに気付けました！
次回はクイックソート。。ということで引き続き頑張っていきます！

※記事内の画像はITを分かりやすく解説から拝借しております。