【プログラミング初心者】Swift練習問題~クイックソート~

クイックソート

クイックソートについて

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

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

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

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

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

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

クイックソートの考え方

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

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

クイックソート1.png

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

クイックソート2.png

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

クイックソート3.png

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

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

クイックソート4.png

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

クイックソート5.png

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

問題

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

回答例はこちら

コメント

タイトルとURLをコピーしました