バブルソートとクイックソート

質問

まだソートについて勉強し始めたばかりですが
バブルソートは対象の総数が増えるとそれに伴い比較回数は増加するのに対し
クイックソートはそれほど増加しないのはなぜでしょうか？？
検索してみてもプログラムが書いてあってよくわからないので...

根本的なところなのでしょうがどなたか教えてください!

回答No.1

kmee · ベストアンサー

では「計算量」というキーワードも追加して検索してください。
また、計算量を表わすのに使われる「オーダー」「ランダウの漸近記法」についても調べてみてください。

おおざっぱに言うと

まじめに比較すれば、
一つ目と残りn-1個の比較
2つ目とそれ以降のn-2個の比較
...
と、要素数nの二乗に比例した回数の比較必要です。これがバブルソートの計算量です。

これを、大きいもの方と小さい方の半分に分けてそれぞれを並び変えれば、
1つの並び換えが(n/2)の二乗= 1/4 * nの2乗
それが大と小の2回で * 2
合わせて 1/4 * nの2乗 * 2
= 1/2 * nの2乗
とバブルソートの半分になります。その半分のものを更に半分に...とやっていくと、最後には n * log2 n に比例する値になります。 これが、クイックソートの計算量です。(正確には平均ですが)

細かい点は省略しているので、最初に書いたような検索の結果や、「アルゴリズム」について詳しく書かれた専門書などを読んでください。

回答No.3

Tacosan

念のためですが....

#2 ではピボットの選び方として「普通は、最初の値や最後の値が使われる」と書かれていますが, これは「アルゴリズムの説明」としてはあり得ても (まあ「アルゴリズムの説明」で最後の値を使うのはかなりひねくれていますが) 「普通に使うため」にはあり得ません. その理由はまさに #2 に書いてある通り「整列されているものに対して適用するとO(n^2)」となってしまうからです. 普通に使うなら「データ列の中央の値を使う」とか「最初と中央と最後のうち真ん中の値のものを使う」とかの選び方をするはずです.

もっともどのような選び方においても「最悪のデータ列」というのは存在するので, 「ピボットの値をランダムに選ぶ」という投げやりな方法をすることもあります.

なお, 本題に対する「大雑把な説明」としては「どちらも一定の条件が成り立つときに 2つのデータの位置を入れ替えるんだけど, どことどこを入れ替えているのかを考えてみる」のがよいかと.

回答No.2

hanabutako

クイックソートはいい具合にランダムにデータが並んでいるという最良の場合にのみO(n log n)になり、整列されているものに対して適用するとO(n^2)です。

クイックソートの手順は、ピボットと呼ばれるデータをまだ大小に分けられていない場所から適当に選び(普通は、最初の値や最後の値が使われる)、それよりも大きい値と小さい値に残りを分け、分けられた中でまた同じ操作を繰り返すというものであるのはご存知かと思います。こうすると、ピボットよりも大きいものと小さいものに一度分けたら、大きいグループの要素と小さいグループの要素を今後は比較しません。つまり、それだけ比較の回数が減ります。バブルソートだとこういうグループ分けが無いので、毎ターン最小値or最大値を残りのグループから探すのに対し、クイックソートでは1/2の領域を更に大小に分けるだけで済みます。n個の要素が毎回綺麗に1/2ずつに分けられていくと、log n回分けることになると思いますが、そのたびに中に入っている要素を整理するのでおおよそ1/2ずつに分けたラウンドで合計n-1回、1/4ずつに分けたラウンドで合計n-3回、...と各ラウンドでざっくり言ってn回の比較が必要になります。よって、O(n log n)です。

...という説明でわかりましたでしょうか？
更にこの手の話を理解したい場合は、分割統治法について調べてみるとよいでしょう。分割統治法自体は、マキャベリの君主論にあるdivide et impera (分割して統治せよ) から来たと言われていますが。

同じく分割統治法のアルゴリズムでは、クイックソートよりはマージソートのほうがわかりやすいですね。クイックソートと違って毎回同じスピートで処理してくれる代わりに倍のメモリーが必要になりますが。