[解決済み] クイックソート ピボットの選択

質問

Quicksortを実装する際に、ピボットを選択する必要があります。しかし、以下のような疑似コードを見ると、どのようにピボットを選択すればよいのかがよくわかりません。リストの最初の要素？他の何か？

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

どなたか、ピボットの選択の概念と、異なるシナリオが異なる戦略を必要とするかどうかを把握するのを助けていただけませんか。

どのように解決するのですか？

ランダムなピボットを選択することで、最悪のケースで O(n ² ) パフォーマンスを最小にします (常に最初か最後を選択すると、ほぼソートされたデータやほぼ逆ソートされたデータで最悪のパフォーマンスが発生します)。 中央の要素を選択することは、ほとんどの場合において許容されるでしょう。

また、これを自分で実装する場合、インプレースで動作するアルゴリズムのバージョンがあります（つまり、2つの新しいリストを作成し、それらを連結することなく）。