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

アルゴリズム

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

挿入ソートとは

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

たとえば、
4,2,5,1,3
とランダムに並んだデータを
1,2,3,4,5
のように昇順に並べ替える場合、

まず先頭のデータをソート済みにします。
  2,5,1,3

そして、残ったデータの先頭のデータ()を、ソート済みデータと順々に比較していきます。
左の数の方が大きい場合は交換し、小さい場合はそのままソート済みにします。
,2  5,1,3(左の方が大きいので交換)

2,  5,1,3

先頭にきたのでソート済みにします。
2,4  5,1,3

同様の処理を繰り返します。
2,,5  1,3(左の方が小さいのでそのままソート済みに)

2,4,5  1,3

2,4,,1  3(左の方が大きいので交換)

2,4,  3(左の方が大きいので交換)

2,4,5  3(左の方が大きいので交換)

1,2,4,5  3(先頭にきたのでソート済みに)

1,2,4,5  3

1,2,4,5,(左の方が大きいので交換)

1,2,4,(左の方が大きいので交換)

1,2,4,5(左の方が小さいのでそのままソート済みに)

1,2,3,4,5

実装

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 文にもどり、同じ処理を繰り返してソートを行います。



参考書

コメント

コンタクトフォーム

    タイトルとURLをコピーしました