syelumd-compressor
シェルソートは、バブルソートと挿入ソートを改良した比較ソートの整列アルゴリズムの一種である

リスト上の離れている要素同士を比較し、最終的に挿入ソートを実行する。

間隔の離れた要素に対してソートを行い、比較する間隔を小さくしながらソートを繰り返すことで単純に近くの要素を比較する場合よりも早く、要素をソートすることができる。


１ 》シェルソート図解

（昇順に並び替える）
  1. 比較/交換する間隔 k を決める
  2. 等間隔 k 左に離れた値と比較/交換を交換できなくなるまで行う
  3. kの値を更新
  4. k = 1まで以上の操作を繰り返す

具体例を次に示す
syel1-compressor
※上記の例では元の配列要素数が少ないため比較/交換間隔kを2から始めている

昇順に並べるため、比較交換は左方向に行う
  1. 比較基準位置h[j]と左にk離れた位置h[j-k]と比較
  2. h[j-k]がh[j]より小さければ交換
  3. jの値をj-kに更新、交換先で1,2の操作を行う
  4. jが0以下になったとき
  5. 比較基準位置（赤旗の位置）を右に1つずらす
  6. 比較基準位置が右端になった時点で比較/交換間隔kを小さい値に更新
  7. 上記の操作を繰り返し、k=1の場合の処理を終えた段階でソート完了

各値を最終目標地点に段階的に近づけていくという操作を行っている。

特徴


  • 比較/交換の間隔、または、その減らし方によって性能が変化
  • 同一キーを持つ要素の順序がソート前後で維持されない
　　→安定なソートではない

計算量


計算量は、比較/交換間隔をどのように取るのかに依存している。

詳しくはこちらなど参考にしてみてください。


２ 》シェルソートプログラム


配列の中身を昇順に並び替える

【JavaScript】
//シェルソートを行う関数
function shellSort(numbers,array_size)
{
    var increment,temp;
    //4離れた要素と比較
    increment = 4;
    
    while(increment > 0)
    {
        for(var i=0;i < array_size;i++)
        {
            var j = i;
            temp = numbers[i];
            
            while((j >= increment) && (numbers[j-increment] > temp))
            {
                numbers[j] = numbers[j - increment];
                j -= increment;
            }
        numbers[j] = temp;
        }
        //incrementを更新
        if(increment/2 != 0)
            increment = parseInt(increment/2);
        else if(increment == 1)
            increment = 0;
        else
            increment = 1;
    }
}

//ここから開始
var h=[6,3,8,4,5,1,2,9,7,0];
document.write("整列前：");
for(var i=0;i < h.length;i++)
{
    document.write(h[i]+" ");
}
document.write("<br>");

//シェルソート
shellSort(h,h.length);

document.write("整列後：");
for(var i=0;i < h.length;i++)
{
    document.write(h[i]+" ");
}

【実行結果】
整列前：6 3 8 4 5 1 2 9 7 0
整列後：0 1 2 3 4 5 6 7 8 9

３ 》その他ソート

  1. 選択ソート
  2. バブルソート
  3. 挿入ソート
  4. マージソート
  5. シェルソート
  6. ヒープソート
  7. クイックソート