今回は選択ソートのアルゴリズムについて、JavaScript でコードをみていきたいと思います。
選択ソートとは
まずソートとはデータを並べ替えることをいい、選択ソートとは、最小値（昇順の場合）をひとつずつ選んで先頭に置くという方法のソートになります。
たとえば、
４，２，５，１，３
とランダムに並んだデータを
１，２，３，４，５
のように昇順に並べ替える場合、
まず全体の中から最小値を選択します。
４，２，５，１，３
そして、それを一番先頭の数と交換し
１，２，５，４，３
ソート済みにします。
１ ２，５，４，３
残った２，５，４，３に対して同様の処理を繰り返します。
最小値を選択し、
２，５，４，３
すでに先頭にあるためそのままソート済みにします。
１，２ ５，４，３
残った５，４，３に対して同様の処理を繰り返します。
最小値を選択し、
５，４，３
先頭の数と交換し
３，４，５
ソート済みにします。
１，２，３ ４，５
残った４，５に対して同様の処理を繰り返します。
最小値を選択し、
４，５
すでに先頭にあるためそのままソート済みにします。
１，２，３，４ ５
残ったデータがひとつだけになったので、そのままソート済みにしてソート完了です。
１，２，３，４，５
実装
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 文にもどり、同じ処理を繰り返してソートを行います。
参考書
コメント