これまでさまざまな並べ替えアルゴリズムについて説明してきましたが、今日は選択並べ替えアルゴリズムについて學(xué)びます。メモリに制約のある環(huán)境で可能な最小限のスワップを可能にする並べ替えアルゴリズム。

目次

1. はじめに
2. 選択ソートアルゴリズムとは何ですか?
3. 選択の並べ替えはどのように機能しますか?
   • 時間計算量
   • 空間の複雑さ
4. JavaScript での実裝
5. leetCode の問題を解決する
6. 結(jié)論

導(dǎo)入

選択ソートは、リストの未ソート部分から最小 (または最大) 要素を繰り返し選択し、それをソート済み部分の先頭 (または末尾) に移動する、シンプルかつ効果的なソート アルゴリズムです。このプロセスは、リスト全體がソートされるまで繰り返されます。この記事では、選択ソート アルゴリズム、JavaScript でのその実裝、および現(xiàn)実世界の問題解決におけるそのアプリケーションについて詳しく説明します。

選択ソートアルゴリズムとは何ですか?

選択ソート アルゴリズムは、インプレース比較ソート アルゴリズムです。入力リストを 2 つの部分に分割します:

1. 左端のソート部分
2. 右端の未整理部分

アルゴリズムは、未ソート部分から最小の要素を繰り返し選択し、それを左端の未ソート要素と交換し、ソート済み部分と未ソート部分の境界を 1 要素右に移動します。

選択の並べ替えはどのように機能しますか?

配列 [64, 25, 12, 22, 11] を使用した例を見てみましょう:

1. 初期配列: [64, 25, 12, 22, 11]

• ソート部分: []
• 未ソート部分: [64, 25, 12, 22, 11]

1. 最初のパス:

• 未ソート部分の最小値を見つける: 11
• 11 をソートされていない最初の要素 (64) と交換します
• 結(jié)果: [11, 25, 12, 22, 64]
• ソート部分: [11]
• 未ソート部分: [25, 12, 22, 64]

1. 2 番目のパス:

• 未ソート部分の最小値を見つける: 12
• 12 をソートされていない最初の要素 (25) と交換します
• 結(jié)果: [11, 12, 25, 22, 64]
• ソートされた部分: [11, 12]
• 未ソート部分: [25, 22, 64]

1. 3 番目のパス:

• 未ソート部分の最小値を見つける: 22
• 22 をソートされていない最初の要素 (25) と交換します
• 結(jié)果: [11, 12, 22, 25, 64]
• ソートされた部分: [11、12、22]
• 未ソート部分: [25, 64]

1. 4 番目のパス:

• 未ソート部分の最小値を見つける: 25
• 25 はすでに正しい位置にあります
• 結(jié)果: [11, 12, 22, 25, 64]
• ソートされた部分: [11、12、22、25]
• 未ソート部分: [64]

1. 最終パス:
   • 殘りの要素は 1 つだけです。自動的に正しい位置に配置されます
   • 最終結(jié)果: [11, 12, 22, 25, 64]

配列は完全にソートされました。

時間計算量

選択ソートの時間計算量は、すべてのケース (最良、平均、最悪) で O(n^2) です。ここで、n は配列內(nèi)の要素の數(shù)です。その理由は次のとおりです。

• 外側(cè)のループは n-1 回実行されます
• 外側(cè)のループの反復(fù)ごとに、內(nèi)側(cè)のループが n-i-1 回実行されます (i は外側(cè)のループの現(xiàn)在の反復(fù)です)

これにより、約 (n^2)/2 の比較と n 回のスワップが行われ、O(n^2) に単純化されます。

この二次時間計算量のため、選択並べ替えは大規(guī)模なデータセットに対して効率的ではありません。ただし、そのシンプルさとスワップの回數(shù)を可能な限り最小限に抑えるという事実により、特定の狀況、特に補助メモリが限られている場合には便利です。

空間の複雑さ

選択ソートは配列をその場でソートするため、空間複雑度は O(1) です。入力サイズに関係なく、一定量の追加メモリ空間のみが必要です。これによりメモリ効率が向上し、メモリに制約のある環(huán)境では有利になります。

JavaScriptでの実裝

これは、選択並べ替えアルゴリズムの JavaScript 実裝です:

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));

コードを分解してみましょう:

1. 配列を入力として受け取る関數(shù)selectionSortを定義します。
2. 外側(cè)のループ (i) で配列を反復(fù)処理します。これは、ソートされた部分とソートされていない部分の境界を表します。
3. 反復(fù)ごとに、ソートされていない最初の要素が最小であると想定し、そのインデックスを保存します。
4. 次に、內(nèi)部ループ (j) を使用して、ソートされていない部分の実際の最小要素を見つけます。
5. より小さい要素が見つかった場合は、minIndex を更新します。
6. 最小値を見つけた後、必要に応じて、それをソートされていない最初の要素と交換します。
7. 配列全體がソートされるまで、このプロセスを繰り返します。

LeetCode の問題の解決

選択ソート アルゴリズムを使用して、leetcode アルゴリズムの問??題を 1 つ解いてみましょう。しましょうか?

問題: 配列のソート [中]

問題: 整數(shù) num の配列を指定して、配列を昇順に並べ替えて返します。組み込み関數(shù)を使用せずに、O(nlog(n)) の時間計算量と可能な限り最小の空間計算量で問題を解決する必要があります。

アプローチ:: この問題を解決するには、選択並べ替えアルゴリズムを直接適用できます。これには、配列を反復(fù)処理し、未ソート部分で最小の要素を見つけて、それを最初の未ソート要素と交換することが含まれます。配列全體がソートされるまで、このプロセスを繰り返します。

解決策:

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));

このソリューションは、以前に実裝した選択並べ替えアルゴリズムを直接適用します。この問題は正しく解決されますが、選択並べ替えの時間の複雑さは O(n^2) であるため、この解決策は LeetCode での大規(guī)模な入力の制限時間を超える可能性があることに注意してください。下の畫像は、解決策は正しいものの、効率的ではないことを示しています。

結(jié)論

結(jié)論として、Selection Sort は、並べ替え技術(shù)の世界への優(yōu)れた入門として機能する、シンプルで直感的な並べ替えアルゴリズムです。そのシンプルさにより、理解と実裝が容易となり、初心者にとって価値のある學(xué)習ツールとなっています。ただし、二次時間計算量が O(n^2) であるため、大規(guī)模なデータセットに対しては効率的ではありません。大規(guī)模なデータセットやパフォーマンスが重要なアプリケーションの場合は、QuickSort、MergeSort、または組み込みの並べ替え関數(shù)などのより効率的なアルゴリズムが推奨されます。

---

---

最新情報を入手してつながりを保つ

このシリーズのどの部分も見逃さないようにし、さらに詳しく知りたい場合は私と連絡(luò)を取ってください
ソフトウェア開発 (Web、サーバー、モバイル、またはスクレイピング / オートメーション)、データに関するディスカッション
構(gòu)造やアルゴリズム、その他のエキサイティングな技術(shù)トピックについては、フォローしてください:

• GitHub
• リンクトイン
• X (Twitter)

コーディングを楽しみにしていてください ????

以上がプロのようにソートアルゴリズムをマスターするの詳細內(nèi)容です。詳細については、PHP 中國語 Web サイトの他の関連記事を參照してください。