今回は挿入ソートのアルゴリズムについて、JavaScript でコードをみていきたいと思います。
挿入ソートとは
まずソートとはデータを並べ替えることをいい、挿入ソートとは、データの並びを保ちながら、適切な位置にデータを挿入していくという方法のソートになります。
たとえば、
4,2,5,1,3
とランダムに並んだデータを
1,2,3,4,5
のように昇順に並べ替える場合、
まず先頭のデータをソート済みにします。
4 2,5,1,3
そして、残ったデータの先頭のデータ(2)を、ソート済みデータと順々に比較していきます。
左の数の方が大きい場合は交換し、小さい場合はそのままソート済みにします。
4,2 5,1,3(左の方が大きいので交換)
↓
2,4 5,1,3
先頭にきたのでソート済みにします。
2,4 5,1,3
同様の処理を繰り返します。
2,4,5 1,3(左の方が小さいのでそのままソート済みに)
↓
2,4,5 1,3
2,4,5,1 3(左の方が大きいので交換)
↓
2,4,1,5 3(左の方が大きいので交換)
↓
2,1,4,5 3(左の方が大きいので交換)
↓
1,2,4,5 3(先頭にきたのでソート済みに)
↓
1,2,4,5 3
1,2,4,5,3(左の方が大きいので交換)
↓
1,2,4,3,5(左の方が大きいので交換)
↓
1,2,3,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 文にもどり、同じ処理を繰り返してソートを行います。
参考書
コメント