挿入ソートとは、配列Aのx番目の追加要素aをxから先頭に向かって比較し、挿入位置を特定する方法。
■実装
var n = 10; var a = []; for(var i = 0; i < n; i++){ a[i] = Math.round(Math.random() * n); } console.log(a); ary = a.concat(); // sort for(var i = 1; i < ary.length; i++){ var val = ary[i]; for(var i2 = i - 1; i2 >= 0; i2--){ if(ary[i2] > val){ ary[i2 + 1] = ary[i2]; } else{ break; } } ary[i2 + 1] = val; } console.log(ary);
■特性
- 最初から集団がほぼ整列しているような場合に適している
- ランダムなデータに対しては効率が悪い
- 計算量が最小となるのは集団が完全に整列していた場合でO(n)である
- 計算量が最大となるのは集団が完全に逆順だった場合でO(n ^ 2)である
- 平均時性能はO(n ^ 2)である。