ソート・アルゴリズム-ソートの選択

5831 ワード
アルゴリズム#アルゴリズム# テキストリンク

整列選択(Seletion Sort)

  • 要素の中で最も高い値が見つかり、一番前の要素と比較してソートされます.
  • を除く最上位の要素では、再び最上位の要素を探し、除外された要素の後の上の違いと比較してソートします.
  • 泡の順序付けとは対照的に、回転が終了するたびに、最も前のデータ位置が決定される.

    • 時間の複雑さ

  • O(n^2):ソートを選択するたびに最大値を探すため、時間の複雑さは常に同じです.

    • 長所

  • 選択ソートもBubble、挿入ソートなどのin placeアルゴリズムで、メモリを節約する利点があり、アルゴリズムは直感的で、理解しやすく、実現しやすい.

    • 短所

  • 選択ソートは、最良でも最悪でもO(n^2)の時間が必要なため、性能が非常に悪い.

    • インプリメンテーション

    'use strict';

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIdx] > arr[j]) {
        minIdx = j;
      }
    }

    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }

  return arr;
}

console.log(
  selectionSort([
    710, 509, 733, 224, 654, 154, 474, 166, 699, 102, 72, 272, 176, 450, 390,
    217, 928, 641, 210, 892,
  ])
);
    常用コードテスト
    [TIL] W4D2 SQL Dialect