JavaScriptアルゴリズム:選択ソート

数値の配列があり、要素サイズで並べ替えたいとします。

オブジェクトの配列を作成したり、年齢による並べ替えや姓のアルファベット順など、オブジェクトのプロパティを比較したりできます。詳細は変わりません。

私たちはこのように働きます:最初のアイテムを選びます。次に、それを2番目の項目と比較します。 2番目のアイテムが小さい場合は、最初のアイテムと交換します。など、この最初のアイテムをと比較しますすべて配列内のアイテム。

最小のアイテムがあることがわかったら、2番目の要素に切り替えて、次の要素と比較します。すべて配列内の項目。インデックス0は最小であることがすでにわかっているため、無視します。など、配列の最後まで続きます。

ご覧のとおり、アルゴリズムは非常に高価です。配列のすべての項目を反復するだけでなく、項目ごとに配列を再度反復します。

その複雑さはO(n^2)。技術的には、比較するアイテムの数は少なくなり続けていますが、これは、複雑さに関するBigOの規則に関しては何の意味もありません。

これが私たちの実装です選択ソート

const selectionSort = (originalList) => {
  //we first copy the array to avoid modifying the original array, since objects are passed by reference in JS
  const list = [...originalList]
  const len = list.length
  for (let i = 0; i < len; i++) {
    let min = i
    for (let j = i + 1; j < len; j++) {
      if (list[min] > list[j]) {
        min = j
      }
    }
    if (min !== i) {
      // a new minimum is found. Swap that with the current element
      ;[list[i], list[min]] = [list[min], list[i]]
    }
  }
  return list
}

const listOfNumbers = [1, 6, 3, 4, 5] console.log(selectionSort(listOfNumbers)) //[1,3,4,5,6]

私の無料ダウンロードJavaScriptビギナーズハンドブック


その他のjsチュートリアル: