JavaScript シェルソート

  • 0
    いいね
  • 0
    コメント

    シェルソート

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

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

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

    手順
    前提 未整列のデータを用意する。
    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()で整数化する