[解決済み] 決定論的クイックソートとは何ですか？

質問

クイックソートについて読んでいると、「決定論的クイックソート」と呼ばれることがあるようです。

これは通常のクイックソートの別バージョンなのでしょうか？ 通常のクイックソートと決定論的クイックソートの違いは何ですか？

解決方法は？

通常の ("deterministic") Quicksort は特定のデータセットに対して非常に悪い振る舞いをすることがあります (例として、ソートされていない最初の要素を選ぶ実装は、すでにソートされたデータに対して O(n^2) 時間複雑度を持ちます)。

ランダムクイックソート（決定論的に選択するのではなく、ランダムにピボットを選択する）を使用すると すべて データセットになります。