insertionmd-compressor
挿入ソート（insertion sort）は、与えられた配列未ソート部の各要素をソート部の正しい位置に挿入していくことで動作する整列アルゴリズム

今回は2通りのソースコードを示す。


１ 》挿入ソート図解

（昇順に並び替える）
  1. 未ソート部の左端の要素をソート部内の要素と比較
  2. ソート部内の要素より小さくなる位置まで未ソート部左端要素を移動
  3. これでソート部の適切な位置に挿入される
  4. この操作を(n - 1)回繰り返す

具体例を次に示す
【1通り目】
比較交換を順次行う方法
sounyu1-compressor
  1. 比較基準要素を未ソート部左端に決める
  2. 1つ左の要素と比較、左の要素より小さければ交換
  3. 交換先でも2の操作を行う
  4. 左の要素が比較要素より大きくなる、または、h[0]に入った時点で完了
  5. 比較基準点を1つ右にずらし未ソート部左端に合わせる
  6. 以上の操作を(h.length - 1)回繰り返す

このやり方では、比較/交換を交互に行う。


【2通り目】
全体をずらす方法
sounyu2-compressor
上の方法と少し違い、挿入位置を先に見つけ、要素をシフトさせ挿入するという方法

  1. 比較基準点の要素とソート部の要素を右から比較していく
  2. 比較基準要素より値が小さくなる位置、または、h[0]を見つける
  3. 変数に比較基準要素を取り出し、ソート部を右に1つシフト
  4. 挿入位置に変数の値を代入
  5. 以上の操作を(h.length - 1)回繰り返す

特徴


  • 選択ソートは数列が整列済みでもO(N^2)の計算量を常に必要とするが、挿入ソートならO(N)で済む
  • 整列対象のデータが追加される状況においても、すでに整列済みのデータを用いて処理を再開できる
　　→オンラインアルゴリズム

  • 同一キーを持つ要素の順序がソート前後で維持される
　　→安定なソート


計算量


データ数をNとすると

合計比較演算回数　N(N - 1)/2

挿入ソートのオーダー　O(N^2)


２ 》挿入ソートプログラム


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

どちらも実行結果は同じです。

【1通り目】
比較交換を交互に繰り返すやり方
//挿入ソートを行う関数
function insertionSort(numbers)
{
    for(var i=1;i < numbers.length;i++) 
    { //整列されていない部分の先頭

        var j = i; 

        // 整列済みの場合処理しない
        while((j > 0) && (numbers[j-1] > numbers[j]))
        {
            //隣り合う要素を交換
            var t;
            t = numbers[j-1];
            numbers[j-1] = numbers[j];
            numbers[j] = t;
            // 隣り合う要素のインデックスを更新
            j--;
        }
    }
}

//ここから開始
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>");

//挿入ソート
insertionSort(h);
 
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


【2通り目】
挿入という形式を分かりやすくしたやり方
//挿入ソートを行う関数
function sounyuSort(hairetu,n)
{
    //値を交換する変数
    var temp;
    
    //比較点をずらす
    for(var i=1;i < n;i++)
    {
        for(var j=0;j < i;j++)
        {
            if(hairetu[i] < hairetu[j])
            {
                temp = hairetu[i];
                //要素を右にずらす
                for(var k=i-1;k >= j;k--)
                {
                    hairetu[k+1] = hairetu[k];
                }
                //jの位置に値を挿入
                hairetu[j] = temp;
            }
        }
    }
}              

//ここから開始
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>");

//挿入ソート
sounyuSort(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. クイックソート