第 5 章では、
という単純な並べ替え方法について説明しました。 バブル仕分け。そのとき、
があると述べられました。 評価が大幅に向上しました。ここでは、最も優れたものの 1 つであるクイック ソート (クイックソート) のバージョンを開発します。
C.A.R. によって発明され、命名された簡単な分類。 Hoare は、現在利用可能な最高の汎用分類アルゴリズムです。クイック ソートの最良の実装は再帰に基づいているため、第 5 章ではそれを示すことができませんでした。私たちが開発するバージョンは文字の配列をソートしますが、ロジックはあらゆる種類のオブジェクトをソートするように適合させることができます。
クイックソートはパーティションの考え方に基づいています。一般的な手順には、比較と呼ばれる値の選択と、配列を 2 つのセクションに分割することが含まれます。パーティション値以上のすべての要素が一方の側に挿入され、小さい要素はもう一方の側に挿入されます。このプロセスは、配列がソートされるまで、残りのセクションごとに繰り返されます。たとえば、配列 fedacb が指定され、値 d を比較として使用すると、クイック ソートの最初のパスで配列が次のように再配置されます。

初期フィーダ
パッセージ 1 b c a d e f

このプロセスは各セクション、つまり bca と def に対して繰り返されます。ご覧のとおり、このプロセスは本質的に再帰的であり、実際、クイック ソートの最もクリーンな実装は再帰的です。
比較値は 2 つの方法で選択できます。ランダムに選択することも、配列から取得した小さな値のセットの平均を見つけることによって選択することもできます。最適な分類を取得するには、値の範囲のちょうど中央にある値を選択する必要があります。ただし、ほとんどのデータセットでこれを行うのは簡単ではありません。最悪のケースは、選択した値が一方の端にある場合です。それでも、クイックソートは正しく実行されます。
私たちが開発するクイック ソートのバージョンでは、配列の中央の要素が比較対象として選択されます。

QSDemo.java を参照してください。

クイックソート:

• 最も効率的で広く使用されている分類アルゴリズムの 1 つ。
• C.A.R.によって発明されました。ホア。
• パーティションの概念に基づいており、配列は再帰的に並べ替えられるセクションに分割されます。
• バブル ソートや他の単純な方法よりも効率的です。

手術：

• 比較値 (ピボット):
• 値が参照 (ピボット) として選択され、配列はその値を中心に編成されます。
• ピボットより小さい要素は一方の側に配置され、大きい要素はもう一方の側に配置されます。
• 配列が完全にソートされるまで、このプロセスがセクションごとに再帰的に繰り返されます。

クイックソート

QSデモ