医学生わくばの欲張り技術ブログ

〜E資格を取りに行く!〜

今日のアルゴリズム(JS実装)〜Shell Sort〜

 どうも、わくばです!

 

 今日はShell Sortを学びました。これはInsertion Sort の応用なのでコードを見てイマイチピントこなかった方は以前書いたInsertion Sortをぜひ参考にしてみてください*1

 

 Shell Sortは飛び飛びでグループを形成し、グループごとにInsertion Sortを繰り返していくソートです。由来に関しては諸説あり、飛び飛びの間隔が徐々に狭まっていく様子が、貝殻のすぼまっていく形状を想起させるという説と、シンプルに「ドナルド=シェル」という方が考案したからという説がありました。

 

 コードはこんな感じです。

const shellSort = array => {
    //間隔を指定
    let gap = Math.floor(array.length / 2);
    //間隔が1になるまで繰り返す
    while(gap>0) {
            //insertion sortを行う
            for (var i = gap; i < array.length; i++) {
                var temp = array[i];
                let j = i;
                while (j >= gap && array[j - gap] > temp ) {
                    array[j] = array[j - gap];
                    j -= gap
                }
                array[j] = temp
            }
        //間隔を狭める    
        gap = Math.floor(gap / 2);
    }
    return array;
}

var array = [8,3,5,9,1,5,9,2,3,8,4,1,5,6,8,4,7,9,5,3,2,6,8,0,4]
console.log(shellSort(array)

>>>[
0, 1, 1, 2, 2, 3, 3, 3,
4, 4, 4, 5, 5, 5, 5, 6,
6, 7, 8, 8, 8, 8, 9, 9,
9
]

 学んできたことが活きている感じがあっていいですね!笑

 

 Complexityは、ギャップが二分割されていくので\(O(logn)\)を考慮し、その中でInsertion Sortが実行されると考えて議論する必要があります。

 Worst-caseでは分割統治でInsertion SortのWorst-caseが実行されるので\(O(n^2logn)\)です。\(logn\)は\(n^2\)と比較すると無限のスケールでは無視できるので\(0(n^2)\)と表記できます。

 Best-caseでは分割統治でInsertion SortのBest-caseが実行されると考えるので\(O(n(logn)^2)\)と表現できます。\(O((logn)^2)\)は増加が緩やかになっていくという性質を表現するだけなら\(O(logn)\)としてしまって、全体で\(O(nlogn)\)と表記することができます。

  Average-caseはギャップ内でいくつスワップが必要になるかに依存しますが、一般に\(O(nlogn)\)と言われます。

 

 

 今日は以上です。ソート全部やってしまおうとか言いましたが、ソートが思った以上に多種あったので驚愕しています。

 

 では。