クイックソートアルゴリズムの解読: 数分で理論から実践まで

クイックソートは、最も高速な並べ替えアルゴリズムの 1 つです。これは値の配列を受け取り、その値の 1 つを「ピボット」要素として選択し、他の値を移動して、より低い値がピボット要素の左側に、より高い値がピボット要素の右側に配置されます。

クイック ソートは、アルゴリズムの世界で最もエレガントで効率的なソート アルゴリズムの 1 つです。バブル ソートや選択ソートのような単純なアルゴリズムとは異なり、クイック ソートは洗練された分割統治戦略を採用しており、実際の処理を大幅に高速化します。マージ ソートも分割統治を使用しますが、クイック ソートの独自のパーティショニング アプローチは、多くの場合、パフォーマンスとメモリ使用量の向上につながります。

平均時間計算量: O(n log n)

最悪の場合の時間計算量: O(n²)

空間の複雑さ: O(log n)

目次

1. クイックソートアルゴリズムとは
2. クイックソートの仕組み
   • 時間計算量
   • 空間の複雑さ
3. JavaScript の実装
4. 結論

クイックソートアルゴリズムとは

クイック ソートは、配列から「ピボット」要素を選択し、ピボットより小さいか大きいかに従って他の要素を 2 つのサブ配列に分割することで機能する、非常に効率的なソート アルゴリズムです。最初に分割して後で結合するマージ ソートとは異なり、クイック ソートはパーティショニング プロセス中にソートを実行します。

他の並べ替えアルゴリズムとの比較を検討してください:

Algorithm	Time Complexity (Average)	Space Complexity	In-Place?
Quick Sort	O(n log n)	O(log n)	Yes
Merge Sort	O(n log n)	O(n)	No
Bubble Sort	O(n²)	O(1)	Yes
Selection Sort	O(n²)	O(1)	Yes
Heap Sort	O(n log n)	O(1)	Yes

クイックソートはどのように機能しますか?

クイック ソート アルゴリズムの JavaScript 実装に入る前に、たった 4 つの簡単な手順で単純な数値の配列を手動でソートすることで、アルゴリズムがどのように機能するかを段階的に理解しましょう。

クイックソートは、次の 4 つの簡単なステップに分けることができます。

1. 配列からピボット要素を選択します。この要素は、リスト/配列の最初、最後、中間、またはランダムな要素である可能性があります。
2. ピボットより小さいすべての要素が左側に配置され、ピボットより大きいすべての要素が右側に配置されるように配列を再配置します。
3. ピボット要素が大きい値の最初の要素と交換して、ピボットが中央に来るようにします。
4. 同じ操作をピボットの左右のサブ配列に再帰的に適用します。

これらの手順を実際の配列に適用してみましょう。しましょうか?

初期配列: [3, 6, 2, 7, 1]

ステップ 1: ピボットを選択する

• 簡単にするために、最後の要素をピボットとして選択します。
• ピボット = 1

ステップ 2: ピボットを中心に配列を再配置する

• ピボット (1) より小さいすべての要素が左側にあり、それより大きいすべての要素が右側にあるように再配置します。
• 各要素を見ていきます:
  • 3 (1 より大きい) → 右側に残ります。
  • 6 (1 より大きい) → 右側に残ります。
  • 2 (1 より大きい) → 右側に残ります。
  • 7 (1 より大きい) → 右側に残ります。
• 再配置された配列: [1, 6, 2, 7, 3]

ステップ 3: ピボットを正しい位置に交換する

• ピボット (1) を、それより大きい最初の要素 (6) と交換します。
• 交換後の配列: [1, 3, 2, 7, 6]
• これで、1 は正しい位置 (インデックス 0) に配置されました。

ステップ 4: サブ配列の再帰的クイックソート

• 左のサブ配列: [] (1 からは要素が残っていないため、ここで並べ替える必要はありません)
• 右サブ配列: [3, 2, 7, 6]

---

右部分配列 [3, 2, 7, 6] を再帰的にソートする

ステップ 1: ピボットを選択する

• ピボット = 6 (最後の要素)

ステップ 2: ピボットを中心に配列を再配置する

• 6 未満の要素を左側に、大きい要素を右側に配置します。
  • 3 (6 未満) → 左側に残ります。
  • 2 (6 未満) → 左側に残ります。
  • 7 (6 より大きい) → 右側に残ります。
• 再配置された配列: [3, 2, 6, 7]

ステップ 3: ピボットを正しい位置に交換する

• 6 はすでに正しい位置 (インデックス 2) にあります。
• 配列: [1, 3, 2, 6, 7]

ステップ 4: サブ配列の再帰的クイックソート

• 左のサブ配列: [3, 2]
• 右サブ配列: [7] (単一要素、ソート不要)

---

左側のサブ配列のソート [3, 2]

ステップ 1: ピボットを選択する

• ピボット = 2 (最後の要素)

ステップ 2: ピボットを中心に配列を再配置する

• 2 未満の要素が左側になるように再配置します。
  • 3 (2 より大きい) → 右側に残ります。
• 再配置された配列: [2, 3]

ステップ 3: ピボットを正しい位置に交換する

• 2 はすでに正しい位置 (インデックス 1) にあります。
• 配列: [1, 2, 3, 6, 7]

ステップ 4: サブ配列の再帰的クイックソート

• 左のサブ配列: [] (要素なし)
• 右サブ配列: [3] (単一要素、ソート不要)

---

最終的にソートされた配列

すべてのサブ配列をソートした後、最終的にソートされた配列を取得します。

ソートされた配列: [1, 2, 3, 6, 7]

以下は、これが実際にどのように機能するかを示す最良の図です:

時間計算量

Quick Sort の時間計算量はピボットの選択によって異なります:

• ベストケース (O(n log n)):

  • ピボットが常に配列を均等に半分に分割するときに発生します
  • Merge Sort のパフォーマンスと同様

• 平均ケース (O(n log n)):

  • 最も実用的なシナリオ
  • キャッシュ使用率が向上するため、マージソートよりも優れています

• 最悪の場合 (O(n²)):

  • すでにソートされた配列と不適切なピボット選択で発生します
  • 優れたピボット選択戦略により回避可能

空間の複雑さ

Quick Sort の空間複雑さは次の理由により O(log n) です:

• 再帰呼び出しスタックの深さ
• インプレースパーティショニング (マージソートの O(n) 追加スペースとは異なります)
• マージソートと比較してメモリ効率が優れています

JavaScriptの実装

function quickSort(arr) {
  // Base case: arrays with length 0 or 1 are already sorted
  if (arr.length <= 1) return arr;

  // Helper function to swap elements
  const swap = (i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  };

  // Partition function using Lomuto's partition scheme
  function partition(low, high) {
    const pivot = arr[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        swap(i, j);
      }
    }
    swap(i + 1, high);
    return i + 1;
  }

  // Main quickSort function implementation
  function quickSortHelper(low, high) {
    if (low < high) {
      const pivotIndex = partition(low, high);
      quickSortHelper(low, pivotIndex - 1); // Sort left side
      quickSortHelper(pivotIndex + 1, high); // Sort right side
    }
  }

  quickSortHelper(0, arr.length - 1);
  return arr;
}

結論

クイックソートは、その効率性とその場でのソートにより人気のある選択肢です。 O(n log n) の平均ケースのパフォーマンスと低いスペースの複雑さにより、バブル ソートや選択ソートなどの単純なアルゴリズムよりも優れたパフォーマンスを発揮します。

重要なポイント:

1. ピボット選択戦略は慎重に選択してください
2. クイック ソートと他のアルゴリズムのどちらを使用するかを決定するときは、入力特性を考慮してください
3. 平均ケースのパフォーマンスを向上させるために、ランダム化されたピボット選択を使用します

---

---

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

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

エマニュエル・アインデフォロー

ソフトウェアエンジニア |テクニカルライター |バックエンド、Web およびモバイル開発者 ? |効率的でスケーラブルなソフトウェア ソリューションの作成に情熱を注いでいます。 #接続しましょう ?

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

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

以上がクイックソートアルゴリズムの解読: 数分で理論から実践までの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。