JavaScript シェルソート

  • 1
    Like
  • 0
    Comment

シェルソート

シェルソートは挿入ソートを改良されてつくられたソートアルゴリズムです。

間隔を空けて挿入ソートを行い、その間隔をだんだんと狭めていきます。
「ドナルド・シェル」さんにちなんでシェルソートと呼ばれます。

基本アイデア
・少ないデータであればソートは速く行える
→データをグループ分けして、少ないデータ量にする
・大雑把でも順番に並んでいる部分が多いと挿入ソートは高速にできる
→間隔を空けてソートすることで「小さい値は一気に前へ、大きい値は一気に後ろへ移動する」効果を利用

手順
前提 未整列のデータを用意する。
1 配列の一定間隔ごとに離れた値をひとつのグループとして考える。間隔の変数(step)を用意して、その範囲を狭めていく。
2 各グループに挿入ソートを行う。挿入ソートは先頭の値を「整列済み」、二つ目以降を「未整列」として処理を開始する。
3 step個のグループができているので、「整列済み」はstep個あることになる。
4 間隔(step)を半分にしていっても、step個以降が「未整列」なおで、ここから挿入ソートを行う。
5 取り出した値をどこに挿入すれば良いのか各グループの後ろからstep間隔で前に向かってみていく。
6 間隔(step)が1つになると全体が1つのグループになる。
7 この状態で挿入ソートを行うと全データに挿入ソートが行われたことになり、整列済みになる。

ポイント
・「グループ分けの間隔を半分にしていく繰り返し」を行う
・その中で「整列していない部分から、挿入する値を順番に1つずつ取り出す」繰り返し
・その中で「取り出した値を、整列した部分のどこに挿入するかを判定する」繰り返し
シェルソートは三重の繰り返しで出来ている

script.js
//未整列のデータ
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)){

    //間隔をあけて挿入ソートを行う
    //挿入する値を1つずつ取り出す繰り返し
    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で割った値」で、それを2で割りながら繰り返す。
割り切れなかった場合を想定して、parseInt()で整数化する