私は最近、どのようにクイックソートが動作するかについてQuick Sort - ComputerphileビデオをYoutubeで見た（紙）と私は質問があります。たとえば、"27,6,19,2,15,9,10"を含む配列があるとします。最初は10をピボットとして選択し、配列は次のようになります：9,2,6 |10| 27,19,15。次に、左のソートされていない配列のピボットとして6を選択し、それは2 |6| 9になり、右のものは19をピボットとして選択し、右のソートされていない配列は15 |19| 27になります。問題は次のとおりです。自分の仕事をより簡単にしたいピボットを選ぶことはできますか（この例のように）、それ以上のものがありますか？クイックソートで必要なピボットを選択できますか？
編集：19の代わりに27をピボットとして選択した場合、配列はどのようになりますか？
this質問と回答をご覧ください。
ほとんどのシナリオでランダムピボットを選択するのがおそらく最良の選択であることを示す議論があります。
パーティションのどの部分も空にならないように任意の値を選択することができます。つまり、最大値より小さくても大きくもない値を選択できます。 （値は配列の要素の1つである必要はありません）。
パーティションのバランスがよくなるほど（中央値に近いほど）、より良い結果が得られます。これは決して行われませんが、算術平均は可能です。
一般的な戦略は、の中央値が3つある（最初と最後と最後の要素）です。
原則として、任意の配列要素をピボットとして使用できます。アルゴリズムは機能します。実際には、配列の最小要素または最大要素をピボットとして選択すると、クイックソートアルゴリズムの1回のパスはほとんど達成されません。 1から100までの数字がランダムな順番であり、1をピボットとして選択すると、ソートするエレメントが99の配列が残ります。最悪の場合は、配列がすでにソートされている場合、最初の配列要素をピボットとしてピッキングすることです。
ランダムピボットは確かに良い選択です。とにかく、短いサブアレイの代替アルゴリズムに切り替えるバージョンでのみ使用してください。さもなければ、乱数生成のコストは重大なオーバーヘッドになる可能性があります。 –
私はその問題を見た。 7要素の配列を持つこの単純なシナリオでは、私のテクニックは良いかどうか？私は最後の質問で質問を更新しました。見てください。 – lor
@ YvesDaoust安い疑似乱数は問題ありません。おそらく単に 'count ++％array.length'を使うことができます。 – Bohemian