【アルゴリズム(JS実装)】Insertion Sort

　どうも、わくばです！

　今日はInsertion Sortです。自分より前の要素を比較していって、自分より小さいものが現れたらその後ろに挿入するというアルゴリズムです。

　コードは以下のような感じです。

const insertionSort = array => {
    for (let i = 1; i < array.length; i++) { 
        //jの位置から比較しながら前に戻っていく
        let j = i; 
        let temp = array[i]; 
        //tempより小さいものがでてくるまでループ
        while (j > 0 && array[j - 1]> temp)  { 
            //自分より大きければ比較対象を後ろにずらす
            array[j] = array[j - 1]; 
            j--;
        }
        //insert位置が決まったらtempをそこまで移動する
        array[j] = temp; 
    }
    return array;
};

array = [4,5,6,3,2,7,12,1];
console.log(insertionSort(array))

結果
[1,2,3,4,5,6,7,12]

　tempに最終的に移動させようとしている変数(array[i])を保持しておき、whileでtempより前の要素を比較していきます。比較対象がtempより大きいものである間は、その比較対象を後ろに一歩ずらし、小さいものが現れた時点でwhileを抜けてその位置にtempを代入するといった流れです。これをforによって各要素で実行していきます。

　Big O notationは\(O(n^2)\)と考えられます。最初から昇順に並んでいれば、各要素のチェックだけで入れ替えはないので\(O(n)\)で済み、逆に降順であればおおよそ\(\dfrac{n(n+1)}{2}\)必要になるので\(O(n^2)\)になります。

　もっとJSの良さを活かしたいなーと、非破壊的なmap()やreduce()などを使ってパターンも考えたりしていますが、一個前のスワップが前提となる処理が多いので非破壊的なメソッドだとそもそも違うアルゴリズムになってしまうんですよね。当たり前ですけど（笑）

　今日は以上です。改善案や、おすすめの面白いアルゴリズムなどありましたら是非コメントください！

　では。