クイックソート

クイックソートのアルゴリズムの概要 どんなケースでも早いソートのアルゴリズムではありません。また、最悪計算時間はn^2になります。 アルゴリズムの手順は以下の通りです。

小さい順で左から並べることを想定する。

1. ランダムにピボットを選択
2. ピボットより左側のデータでピボットより大きいものを右側に右側のデータで小さいものを左側に交換する。
3. 交換を終えたら、そのピボットの値を確定して、分割された右側と左側のそれぞれで1.からを繰り返す.

Quickソートではピボットの選択によって最悪ケースになるかどうかが決まる。 その最悪ケースは、ピボットがソートする列の最大か最小を選んだ時なので、同一の値が多い時等は、そのケースにハマりやすく遅くなりやすいです。 実装次第ですが、既にソートされているものや逆順にソートされているものにおいて最初のピボットを選んでしまう場合も遅くなります。

大方並び終えた時に挿入ソートに変更して高速化することがなどが頻繁に 行われる。