【アルゴリズム(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)\)と言われます。
今日は以上です。ソート全部やってしまおうとか言いましたが、ソートが思った以上に多種あったので驚愕しています。
では。