Algorithm - CodeKata # 21

1.ソートの選択（Selection Sort）

ソートアルゴリズムは、無秩序なデータを順番に並べ替えるアルゴリズムです.
ソートの方法はいろいろありますが、その中でも有名なアルゴリズムは以下の4種類あります.

選択ソート

泡順

挿入ソート

クイックソート

今日は選択ソートを学びます.
「ソート」を選択し、ソートされていないデータの中で最小のデータを選択します.
先頭から順番に並べられたアルゴリズム.
英語の説明を見てみましょう.
It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.
Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
例を見てみましょう.

並べ替えが必要な配列は[7,5,4,2]である.
最初のループはindex 0から3をチェックし、最小数を検索します.
index 0の7を置き換えます.2です.->[2,5,4,7]
2番目のオプションはindex 1から3をチェックし、最小の数値を検索します.
インデックス1の5(4)->[2,4,5,7]を置換
3つ目はindex 2から3...このようにして最小の数を選択し、順番に置き換えることを選択ソートと呼ぶ.

2. Question

numsという名前のソートされていない数値配列を指定した場合は、昇順(1,2,3.10)でソートされた配列を返します.
選択ソートアルゴリズムで実現すべきでしょう?

3. Answer

const selectionSort = (nums) => {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] > nums[j]) {
        let bigger = nums[i];
        nums[i] = nums[j];
        nums[j] = bigger;
      }
    }
  }
  return nums;
}

console.log(selectionSort([2, 7, 3, 1, 10])); // [ 1, 2, 3, 7, 10 ]

Ref

JavaScript配列順序の変更[スワップ]