メモログ

塵が積もって山とならないメモのログ

Insertion Sort in JavaScript

Selection Sort in JavaScriptの記事から引き続き。内容は挿入ソートからの抜粋なので詳細はそちらを参照。

挿入ソートは配列から左から順に値を取り出して、ソート済みの配列の適切な場所に値を挿入していく、ということを繰り返し行う。配列は左から順にソート済み状態となり、最後までソート済みになったところで終了。選択ソートと同じO(n^2)であるけど、選択ソートが取り出す値を見つけるのにソートされていない値をすべて確認しなければならないのに対して、挿入ソートはソート済みの値を比較して挿入位置が見つかったらそこで確認を終えることができる。ので、挿入ソートの方が実際の効率は良いとされている。

実装例はThe Insertion sort algorithm - Ben’s BlogとV8のarray.jsを参考にしている。

テストの箇所は省略。Gistを参照してください。今回は前回のSelection Sort in JavaScriptと同じ配列を使って比較してみた。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function insertionSort(array, showArray) {
  let count = 0;
  const arrayLength = array.length;
  for (let i=1; i<arrayLength; i++) {
    const a = array[i];
    let j = i-1;
    for (; j>=0; j--) {
      count++;
      const b = array[j];
      if (a < b) {
        array[j+1] = b
      } else {
        break;
      }
    }
    array[j+1] = a;
    if (showArray) {
      console.log(array);
    }
  }
  console.log(`number of iterates: ${count}`);
}

実行例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
> test([bubbleSort, selectionSort, insertionSort], 10, true);
---- bubbleSort ----
[ 8020, 3904, 5318, 5951, 5754, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 5318, 5951, 5754, 8020, 8284, 7898, 4501, 5629, 9043 ]
[ 3904, 5318, 5754, 5951, 8020, 7898, 4501, 5629, 8284, 9043 ]
[ 3904, 5318, 5754, 5951, 7898, 4501, 5629, 8020, 8284, 9043 ]
[ 3904, 5318, 5754, 5951, 4501, 5629, 7898, 8020, 8284, 9043 ]
[ 3904, 5318, 5754, 4501, 5629, 5951, 7898, 8020, 8284, 9043 ]
[ 3904, 5318, 4501, 5629, 5754, 5951, 7898, 8020, 8284, 9043 ]
[ 3904, 4501, 5318, 5629, 5754, 5951, 7898, 8020, 8284, 9043 ]
number of iterates: 43
sorting: 0.375ms

---- selectionSort ----
[ 8020, 3904, 5318, 5951, 5754, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 8020, 5318, 5951, 5754, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 4501, 5318, 5951, 5754, 8284, 9043, 7898, 8020, 5629 ]
[ 3904, 4501, 5318, 5951, 5754, 8284, 9043, 7898, 8020, 5629 ]
[ 3904, 4501, 5318, 5629, 5754, 8284, 9043, 7898, 8020, 5951 ]
[ 3904, 4501, 5318, 5629, 5754, 8284, 9043, 7898, 8020, 5951 ]
[ 3904, 4501, 5318, 5629, 5754, 5951, 9043, 7898, 8020, 8284 ]
[ 3904, 4501, 5318, 5629, 5754, 5951, 7898, 9043, 8020, 8284 ]
[ 3904, 4501, 5318, 5629, 5754, 5951, 7898, 8020, 9043, 8284 ]
[ 3904, 4501, 5318, 5629, 5754, 5951, 7898, 8020, 8284, 9043 ]
number of iterates: 45
sorting: 0.477ms

---- insertionSort ----
[ 8020, 3904, 5318, 5951, 5754, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 8020, 5318, 5951, 5754, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 5318, 8020, 5951, 5754, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 5318, 5951, 8020, 5754, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 5318, 5754, 5951, 8020, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 5318, 5754, 5951, 8020, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 5318, 5754, 5951, 8020, 8284, 9043, 7898, 4501, 5629 ]
[ 3904, 5318, 5754, 5951, 7898, 8020, 8284, 9043, 4501, 5629 ]
[ 3904, 4501, 5318, 5754, 5951, 7898, 8020, 8284, 9043, 5629 ]
[ 3904, 4501, 5318, 5629, 5754, 5951, 7898, 8020, 8284, 9043 ]
number of iterates: 29
sorting: 0.432ms

配列の数が10件くらいだと他のソートと比較してそこまで変わらない感じだけど（console.logで途中経過を出力しているせいもある）、繰り返しテストしてみても挿入ソートがわずかに速い感じはある。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
>  test([bubbleSort, selectionSort, insertionSort], 10000);
---- bubbleSort ----
number of iterates: 49965117
sorting: 181.487ms
---- selectionSort ----
number of iterates: 49995000
sorting: 142.477ms
---- insertionSort ----
number of iterates: 24947072
sorting: 62.062ms

> test([bubbleSort, selectionSort, insertionSort], 10000);
---- bubbleSort ----
number of iterates: 49967415
sorting: 187.717ms
---- selectionSort ----
number of iterates: 49995000
sorting: 133.253ms
---- insertionSort ----
number of iterates: 25001157
sorting: 68.090ms

> test([bubbleSort, selectionSort, insertionSort], 10000);
---- bubbleSort ----
number of iterates: 49925349
sorting: 184.928ms
---- selectionSort ----
number of iterates: 49995000
sorting: 131.695ms
---- insertionSort ----
number of iterates: 24960792
sorting: 66.688ms

配列の数が10000件になると挿入ソートの実行時間が顕著に少なくなる。ざっと見た雰囲気では100件くらいでも差が出てくる。

派生形としてShell sortがあり、こちらは間隔(gap)をあけた数値同士で挿入ソートをしつつ、だんだんその間隔を狭くして挿入ソートを実行していく。

動画では、gapを5, 3, 1と狭めつつソートを実行している。このgapをどうやって決めるかのが難しくて、いろいろな決め方が提案されている。complexityもgapの取り方が変わるようで一意的には決まらないようである。

Binary Insertion Sortは、挿入する位置を探すのにBinary Searchを使う。探すのにかかるコストはO(n log n)になる。とはいえ必要なswapにかかるコストがO(n^2)なので、全体もO(n^2)のままになる。値が移動する位置をあらかじめ計算しておくことで、swapの回数を減らすことができる。

ChakraCoreの実装ではBinary Insertion Sortを使っていて、要素のswapはMoveArrayメソッドのところで、memmoveを使って移動させている。

そのほかLink listやSkip Listを使ってswapの回数を減らす方法も紹介されている。

以上。