今回は選択ソートのアルゴリズムについて、JavaScript でコードをみていきたいと思います。
選択ソートとは
まずソートとはデータを並べ替えることをいい、選択ソートとは、最小値(昇順の場合)をひとつずつ選んで先頭に置くという方法のソートになります。
たとえば、
4,2,5,1,3
とランダムに並んだデータを
1,2,3,4,5
のように昇順に並べ替える場合、
まず全体の中から最小値を選択します。
4,2,5,1,3
そして、それを一番先頭の数と交換し
1,2,5,4,3
ソート済みにします。
1 2,5,4,3
残った2,5,4,3に対して同様の処理を繰り返します。
最小値を選択し、
2,5,4,3
すでに先頭にあるためそのままソート済みにします。
1,2 5,4,3
残った5,4,3に対して同様の処理を繰り返します。
最小値を選択し、
5,4,3
先頭の数と交換し
3,4,5
ソート済みにします。
1,2,3 4,5
残った4,5に対して同様の処理を繰り返します。
最小値を選択し、
4,5
すでに先頭にあるためそのままソート済みにします。
1,2,3,4 5
残ったデータがひとつだけになったので、そのままソート済みにしてソート完了です。
1,2,3,4,5
実装
let nums = [4,2,5,1,3];//これを選択ソートする
for (let i = 0; i < nums.length; i++) {
let min = i;
for (let j = i+1; j < nums.length; j++) {
if (nums[min] > nums[j]) {
min = j;
}
}
if (i != min) {
let temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
}
console.log(nums);//[1,2,3,4,5]と表示
解説
最初の for 文で、データをひとつずつ調べます。
for (let i = 0; i < nums.length; i++) {
...
}
まずは、先頭のデータが最小値であると仮定します。
(min は最小値が何番目かを示す)
let min = i;
そして残りのデータを調べ、min 番目のデータよりも小さいものがあれば、min を上書きします。
for (let j = i+1; j < nums.length; j++) {
if (nums[min] > nums[j]) {
min = j;
}
}
残りのデータを調べた結果、もし先頭のデータが最小値でなければ、先頭のデータと最小値のデータを入れ替えます。
if (i != min) {
let temp = nums[i];
nums[i] = nums[min];
nums[min] = temp;
}
そして最初の for 文にもどり、同じ処理を繰り返してソートを行います。
参考書
コメント