挿入ソート

ソートのアルゴリズムは、理解するのはそれほど苦労しないのですが実際にコードに落とし込む段階でいつもつまずくので記録して書き残しておこうと思います。概要は下記。その他解説ページは世の中にあふれていますのでそちらを参照していただければと思います。

// 挿入ソート Javascript
function insertionSort(A) {
  var N = A.length;
  
  for (var j = 1; j < N; j++) {
    var ins = A[j];
    var i = j - 1;
  
    while (i >= 0 && ins < A[i]) {
      A[i + 1] = A[i];
      i = i - 1;
    }
    
    A[i + 1] = ins;

  }
  return A;
}

insertionSort[ 5, 2, 9, 1, 4 ]

この記事では挿入ソート（上記）のコードをねちっこく見ていこうと思っています。JavaScriptです。

  for (var j = 1; j < N; j++) {
    var ins = A[j];
    var i = j - 1;

上記のforループでは、j = 1から開始。j = 0の場合だと要素が１つだけなので比較やソートできないため。ポイントは var ins = A[ j ] の部分で、挿入する要素をins変数に代入しています。ループの最後でこの数値を適切な場所に戻すことになります。i = j - 1として、インデックス番号jと比較する対象になります。

    while (i >= 0 && ins < A[i]) {
      A[i + 1] = A[i];
      i = i - 1;
    }

そして挿入ソートの本丸, whileループ。

    while (i >= 0 && ins < A[i]) {

この１行で「 i が 0 以上かつ ins が A[ i ] より大きい」という条件を満たした場合という条件付きでwhileループが記述されています。

これが何を調べているのか細かく見ていきます。

i >= 0

この１行は配列の先頭（＝インデックス０）を超えていないか確認。超えている(= インデックスが０より小さい)部分には要素が存在しないのでループ処理をする意味がない。

ins < A[i]

この１行は、挿入したい値（ins）が、現在見ている値（ A[ i ] ）より小さいか確認。この条件は、新しい要素（ins）をどこに挿入すべきかを決定するために使用されます。insより大きい要素を見つけた場合、その要素（とそれ以前の要素）は右にシフトするし、insより小さいか等しい要素を見つけた時点で、その直後が正しい挿入位置となります。もしこの条件がなければ、アルゴリズムは常に配列の先頭まで要素をシフトしてしまうので、それを防ぐ役割も。

A[i + 1] = A[i];

while ループ中の記述です。新しい要素（ins）を挿入するための空間を作りつつ、ソート済みの部分で、新しい要素より大きい要素を右に移動させています。具体的には、A[i]の値を、その右隣のA[i + 1]にコピーし、結果として、A[i]の値が右に1つ移動したことになります。whileループ内でこの操作を繰り返すことで、必要な数だけ要素を右にシフトすることができます。

i = i - 1;

i の値を小さくしていくことで、調べる範囲を左に拡大していきます。

A[i + 1] = ins;

このコードはwhileループ終了後に実行されます。whileループでinsより大きい全ての要素が右にシフトされているので、その後にこのコードを実行することで、insが正しい位置に挿入されます。whileループが終了した時点で、iはinsより小さい（または等しい）最後の要素のインデックスを指しているので、i + 1が新しい要素（ins）の正しい位置になっています。

for (var j = 1; j < N; j++) {

そして再びforループが始まり、範囲を広げて同じ処理が繰り返されることになります。これを繰り返して、すべての処理が終了すると配列の要素が小さい順に並び変わっているというものです。

挿入ソートの時間計算量 (time complexity)

最悪の場合: O(n^2)
入力配列が逆順にソートされている場合。[5, 4, 3, 2, 1]など。
　外部ループ: n-1回実行（nは配列の要素数）
　内部ループ: 最悪の場合、各要素を配列の先頭まで移動
　結果: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 の比較操作

平均の場合: O(n^2)
ランダムな順序の入力配列の場合

最良の場合: O(n)
入力配列が既にソートされている場合。[1, 2, 3, 4, 5]など。

挿入ソートの空間計算量 (space complexity)

O(1)（定数空間）

結論

挿入ソートは、時間計算量が最悪でも平均でもO(n^2)であり、大規模なデータセットには適していない。ただし空間効率が O(1)とよいため、小規模なデータなどには効果的と言えるかも？