クイックソート

クイックソートについて

クイックソートはソートアルゴリズムの１つです。

過去の投稿で一度ソートの実装問題を出していますが、回答例ではバブルソートと呼ばれるソートアルゴリズムで実装をしています。
バブルソート:https://qiita.com/euJcIKfcqwnzDui/items/306979a03fc813615720

ソートアルゴリズムにはバブルソート、マージソート、クイックソートなど複数のアルゴリズムがあります。
なぜ複数あるのかというと計算量の違いです。
この計算量の違いにより、処理速度に差が出てしまうためより早いソートアルゴリズムが求められています。

その中で最も早いと言われているのがクイックソートと呼ばれるアルゴリズムです。
(データの並びによって変わるため必ずしも最速となるわけではありません)

N個の配列の場合、バブルソートでは要素数に対して二重ループを回しているため計算量はN^2程度です。
一方でクイックソートの場合の計算量はNlogNとなり、大幅に改善されます。
※計算量はOという記号で表され、O(N^2)、O(NlogN)と記載されます。(オーダーと呼びます)

クイックソートの計算量に興味が有る方は調べてみると多くの解説があります。

クイックソートの考え方

クイックソートの考え方について紹介します。

以下のような配列が与えられているとします。

クイックソートではまずピボットと呼ばれる軸となる数値を配列の中から１つ決めます。
決め方は何でも構いません。
今回は配列の先頭をピボットとします。

ピボットを決めたら各要素に対し前から順に比較を行ない、大きいグループ、小さいグループに分割します。

これでピボットから見て左は大きいグループ、右は小さいグループと大雑把なソートができています。
つまり当然ですが[大きいグループの値]>[右は小さいグループの値]となるため、今後大きいグループの値はピボットより右に、小さいグループの値はピボットより左にくることはあり得ません。
そのため次からは各グループ内でのみ並べ替えを行えばよくなります。