クイックソート

クイックソートについて

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

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

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

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

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

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

クイックソートの考え方

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

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

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

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

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

次の処理では各グループ内でそれぞれ新しくピボットを決めます。
それぞれ決めたピボットに対しその中でさらに大きいグループ、小さいグループに振り分けます。

これを分割したグループに要素が存在する限り続けます。

このように最後まで並べ替え続けるとソート完了となります。

問題

降順ソートを行う関数をクイックソートを用いて作成してください。

回答例はこちら

最後に

別の問題は以下に掲載しています。
また本記事とは別でプログラミング未経験からiOSアプリ開発が行えるようになることを目的とした記事を連載しています。
連載も以下にまとめていますのでそちらも是非もご覧ください。
http://naoyalog.com/