シェルソート
シェルソートは挿入ソートを改良されてつくられたソートアルゴリズムです。
間隔を空けて挿入ソートを行い、その間隔をだんだんと狭めていきます。
「ドナルド・シェル」さんにちなんでシェルソートと呼ばれます。
基本アイデア
・少ないデータであればソートは速く行える
→データをグループ分けして、少ないデータ量にする
・大雑把でも順番に並んでいる部分が多いと挿入ソートは高速にできる
→間隔を空けてソートすることで「小さい値は一気に前へ、大きい値は一気に後ろへ移動する」効果を利用
手順
前提 未整列のデータを用意する。
1 配列の一定間隔ごとに離れた値をひとつのグループとして考える。間隔の変数(step)を用意して、その範囲を狭めていく。
2 各グループに挿入ソートを行う。挿入ソートは先頭の値を「整列済み」、二つ目以降を「未整列」として処理を開始する。
3 step個のグループができているので、「整列済み」はstep個あることになる。
4 間隔(step)を半分にしていっても、step個以降が「未整列」なおで、ここから挿入ソートを行う。
5 取り出した値をどこに挿入すれば良いのか各グループの後ろからstep間隔で前に向かってみていく。
6 間隔(step)が１つになると全体が１つのグループになる。
7 この状態で挿入ソートを行うと全データに挿入ソートが行われたことになり、整列済みになる。
ポイント
・「グループ分けの間隔を半分にしていく繰り返し」を行う
・その中で「整列していない部分から、挿入する値を順番に１つずつ取り出す」繰り返し
・その中で「取り出した値を、整列した部分のどこに挿入するかを判定する」繰り返し
シェルソートは三重の繰り返しで出来ている
//未整列のデータ
var a = [10,3,1,9,7,6,8,2,4,5];
//「グループ分けの間隔を半分にしていく繰り返し」
for(var step = parseInt(a.length/2); step > 0; step = parseInt(step/2)){
//間隔をあけて挿入ソートを行う
//挿入する値を１つずつ取り出す繰り返し
for(var i = step; i < a.length; i++){
//挿入する値を一時的に保存する
var tmp = a[i];
//取り出した位置から前に向かって比較するfor文
for(var j = i; j >= step; j -= step){
if(a[j-step]>tmp){
//挿入する値が小さい場合、その値をstep幅だけ後ろへずらす
a[j] = a[j - step];
}else{
//挿入する値が小さくなければ、処理を止める
break;
}
}
//ずらす処理が終わったところに「挿入する値」をいれる
a[j] = tmp;
}
}
//ソート後の値を表示
console.log(a);
補足
間隔(step)の最初は「配列の個数を２で割った値」で、それを2で割りながら繰り返す。
割り切れなかった場合を想定して、parseInt()で整数化する