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

アルゴリズム

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

選択ソートとは

まずソートとはデータを並べ替えることをいい、選択ソートとは、最小値(昇順の場合)をひとつずつ選んで先頭に置くという方法のソートになります。

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

まず全体の中から最小値を選択します。
4,2,5,,3

そして、それを一番先頭の数と交換し
,2,5,4,

ソート済みにします。
  2,5,4,

残った2,5,4,3に対して同様の処理を繰り返します。
最小値を選択し、
,5,4,3

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

残った5,4,3に対して同様の処理を繰り返します。
最小値を選択し、
5,4,

先頭の数と交換し
,4,5

ソート済みにします。
1,2,3  4,5

残った4,5に対して同様の処理を繰り返します。
最小値を選択し、
,5

すでに先頭にあるためそのままソート済みにします。
1,2,3  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 文にもどり、同じ処理を繰り返してソートを行います。




参考書

コメント

コンタクトフォーム

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