【JavaScriptでアルゴリズム】並び替え（挿入ソート）

今回は挿入ソートのアルゴリズムについて、JavaScript でコードをみていきたいと思います。

挿入ソートとは
実装
解説

挿入ソートとは

まずソートとはデータを並べ替えることをいい、挿入ソートとは、データの並びを保ちながら、適切な位置にデータを挿入していくという方法のソートになります。

たとえば、
４，２，５，１，３
とランダムに並んだデータを
１，２，３，４，５
のように昇順に並べ替える場合、

まず先頭のデータをソート済みにします。
４　　２，５，１，３

そして、残ったデータの先頭のデータ（２）を、ソート済みデータと順々に比較していきます。
左の数の方が大きい場合は交換し、小さい場合はそのままソート済みにします。
４，２　　５，１，３（左の方が大きいので交換）
↓
２，４　　５，１，３

先頭にきたのでソート済みにします。
２，４　　５，１，３

同様の処理を繰り返します。
２，４，５　　１，３（左の方が小さいのでそのままソート済みに）
↓
２，４，５　　１，３

２，４，５，１　　３（左の方が大きいので交換）
↓
２，４，１，５　　３（左の方が大きいので交換）
↓
２，１，４，５　　３（左の方が大きいので交換）
↓
１，２，４，５　　３（先頭にきたのでソート済みに）
↓
１，２，４，５　　３

１，２，４，５，３（左の方が大きいので交換）
↓
１，２，４，３，５（左の方が大きいので交換）
↓
１，２，３，４，５（左の方が小さいのでそのままソート済みに）
↓
１，２，３，４，５

実装

let nums = [4,2,5,1,3];//これを挿入ソートする

for (let i = 1; i < nums.length; i++) {
  for (let j = i-1; j >= 0; j--) {
    if (nums[j] > nums[j+1]) {
      let temp = nums[j];
      nums[j] = nums[j+1];
      nums[j+1] = temp;
    }
  }
}
console.log(nums);//[1,2,3,4,5]と表示

解説

最初の for 文は、ふたつめ以降のデータを順次調べていくためのものです。

for (let i = 1; i < nums.length; i++) {
...
}

次の for 文と if 文で、ソート済みデータとひとつずつ比較していき、適宜交換を行います。

  for (let j = i-1; j >= 0; j--) {
    if (nums[j] > nums[j+1]) {
      let temp = nums[j];
      nums[j] = nums[j+1];
      nums[j+1] = temp;
    }
  }

そして最初の for 文にもどり、同じ処理を繰り返してソートを行います。

参考書