マージソートと同様に、QuickSortは分割統治アルゴリズムです。要素をピボットとして選択し、選択したピボットの周りに指定された配列を分割します。さまざまな方法でピボットを選択するquickSortにはさまざまなバージョンがあります。
- 常に最初の要素をピボットとして選択します。
- 常に最後の要素をピボットとして選択します（以下に実装）
- ランダムな要素をピボットとして選択します。
- ピボットとして中央値を選択します。
quickSortの重要なプロセスはpartition（）です。パーティションのターゲットは、配列と配列の要素xをピボットとして指定し、xを並べ替えられた配列の正しい位置に配置し、すべての小さい要素（xより小さい）をxの前に配置し、すべての大きい要素（xより大きい）をxの後に配置します。バツ。これはすべて線形時間で実行する必要があります。
再帰クイックソート関数の擬似コード：
パーティションアルゴリズム
擬似コードがCLRSブックに記載されている方法を採用しているため、パーティションを作成する方法は多数あります。ロジックは単純です。左端の要素から開始し、小さい（または等しい）要素のインデックスをiとして追跡します。トラバース中に、小さい要素が見つかった場合は、現在の要素をarrと交換します。それ以外の場合は、現在の要素を無視します。
partition（）の擬似コード
partition（）の図：
実装：
QuickSortの実装は次のとおりです：
出力：
Sorted array:1 5 7 8 9 10
QuickSortの分析
クイックソートが一般的にかかる時間は次のように書くことができます。
T(n) = T(k) + T(n-k-1) + (n)
最初の2つの用語は、2つの再帰呼び出し用であり、最後の用語は、パーティションプロセス用です。 kは、ピボットよりも小さい要素の数です。
QuickSortにかかる時間は、入力配列とパーティション戦略によって異なります。以下は3つのケースです。
最悪のケース：最悪のケースは、パーティションプロセスが常に最大または最小の要素をピボットとして選択する場合に発生します。最後の要素が常にピボットとして選択される上記のパーティション戦略を検討すると、配列がすでに昇順または降順で並べ替えられている場合に最悪のケースが発生します。以下は最悪の場合の再発です。
T(n) = T(0) + T(n-1) + (n)which is equivalent to T(n) = T(n-1) + (n)
上記の繰り返しの解決策は（n2）です。
ベストケース：ベストケースは、パーティションプロセスが常にピボットとしての中央の要素。以下は、最良の場合の再発です。
T(n) = 2T(n/2) + (n)
上記の再発の解決策は（nLogn）です。マスター定理のケース2を使用して解決できます。
平均ケース：
平均ケース分析を行うには、配列のすべての可能な順列を考慮し、そうでないすべての順列にかかる時間を計算する必要があります。
パーティションがO（n / 9）要素を1つのセットに配置し、O（9n / 10）要素を別のセットに配置する場合を検討することで、平均的なケースのアイデアを得ることができます。以下は、この場合の再発です。
T(n) = T(n/9) + T(9n/10) + (n)
上記の再発の解決策もO（nLogn）です
クイックソートの最悪の場合の時間計算量はO（n2）ですが、は、マージソートやヒープソートなどの他の多くのソートアルゴリズムよりも優れています。QuickSortは、内部ループをほとんどのアーキテクチャとほとんどの実世界のデータに効率的に実装できるため、実際には高速です。クイックソートは、ピボットの選択を変更することでさまざまな方法で実装できるため、特定のタイプのデータで最悪のケースが発生することはめったにありません。ただし、データが巨大で外部ストレージに保存されている場合は、通常、マージソートの方が適していると考えられます。
QuickSortは安定していますか？
デフォルトの実装は安定していません。ただし、インデックスを比較パラメーターと見なすことで、任意の並べ替えアルゴリズムを安定させることができます。
クイックソートはインプレースですか？
インプレースアルゴリズムの広義の定義によれば、追加で使用するため、インプレース並べ替えアルゴリズムとしての資格があります再帰的な関数呼び出しを格納するためだけのスペースで、入力を操作するためのスペースではありません。
リンクリストにQuickSortを実装する方法は？
単一リンクリストのQuickSort
二重リンクリストのQuickSort
QuickSortを反復的に実装できますか？
はい、反復クイックソートを参照してください。
配列のソートにMergeSortよりもクイックソートが優先される理由
一般的な形式のクイックソートはインプレースソートです（つまり、追加のストレージは必要ありません）が、マージソートにはO（N）の追加ストレージが必要であり、Nは非常に高価なアレイサイズを示します。マージソートに使用される余分なスペースの割り当てと割り当て解除により、アルゴリズムの実行時間が長くなります。平均の複雑さを比較すると、両方のタイプのソートの平均の複雑さはO（NlogN）ですが、定数は異なります。配列の場合、追加のO（N）ストレージスペースを使用するため、マージソートは失われます。
クイックソートの最も実用的な実装では、ランダム化されたバージョンを使用します。ランダム化バージョンでは、O（nLogn）の時間計算量が予想されていました。最悪のケースはランダム化バージョンでも発生する可能性がありますが、特定のパターン（ソートされた配列など）では最悪のケースは発生せず、ランダム化されたクイックソートは実際にはうまく機能します。
クイックソートはキャッシュフレンドリーソートでもあります配列に使用すると参照の局所性が高いため、アルゴリズム。
クイックソートも末尾再帰であるため、末尾呼び出しの最適化が行われます。
リンクリストのQuickSortよりもMergeSortが優先される理由？
リンクリストの場合、主に配列とリンクリストのメモリ割り当ての違いにより、ケースが異なります。配列とは異なり、リンクリストノードはメモリ内で隣接していない場合があります。配列とは異なり、リンクリストでは、O（1）の余分なスペースとO（1）の時間の中央にアイテムを挿入できます。したがって、マージソートのマージ操作は、リンクリスト用の余分なスペースなしで実装できます。
配列では、要素がメモリ内で連続しているため、ランダムアクセスを実行できます。整数（4バイト）の配列Aがあり、Aのアドレスをxとすると、Aにアクセスするには、（x + i * 4）のメモリに直接アクセスできます。配列とは異なり、リンクリストでランダムアクセスを行うことはできません。クイックソートには、この種のアクセスがたくさん必要です。リンクリストでi番目のインデックスにアクセスするには、メモリの連続ブロックがないため、すべてのノードをヘッドからi番目のノードに移動する必要があります。したがって、クイックソートのためにオーバーヘッドが増加します。マージソートはデータに順次アクセスし、ランダムアクセスの必要性は低いです。
QuickSortを最適化して、最悪の場合にO（Log n）の余分なスペースを使用する方法は？
QuickSortテールコールの最適化（最悪の場合のスペースをLog nに減らす）
スナップショット：
- QuickSortのクイズ
- QuickSortの最近の記事
- ソート。
GeeksforGeeks / GeeksQuizの他のソートアルゴリズム：
選択ソート、バブルソート、挿入ソート、マージソート、ヒープソート、クイックソート、Radixソート、Countingソート、Bucketソート、ShellSort、Combソート、Pigeonholeソート