デュアルピボットクイックソート

クイックソートアルゴリズムの改善： iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf



短い説明：

通常のクイックソートは、配列を2つのセグメントに分割し、ランダムな要素Pを選択します。次に、P未満のすべての要素が最初のセグメントに、残りが2番目のセグメントに収まるように配列をソートします。 次に、アルゴリズムは最初と2番目のセグメントで再帰的に繰り返されます。



デュアルピボットクイックソートは、配列を2つではなく3つのセグメントに分割します。 その結果、移動する配列要素の操作数が大幅に削減されます。



PDFで、アルゴリズムの作成者は、アルゴリズムとJavaでの実装のより詳細な説明を提供します。