挿入ソートとクイックソートの平均計算量の違いについて

Question

情報系の学生です。
クイックソートが挿入ソートよりも一般的にはやい理由の説明について質問があります。（クイックソートが遅くなることもありますが今回は考えません）

今度、挿入ソートよりクイックソートのほうが一般的に早い理由を説明する機会があります。
そこで、今現在考えているのが

「挿入ソートが一回の操作で要素を1つ正しい場所に置くことしかできないのに対し、クイックソートでは基本的に一回の操作で、グループを大きく二つに分けていくので分割を行うたびに要素数が減り比較回数が減っていく。結果として挿入ソートより早くなることが多い」
という説明で間違いはないでしょうか

そもそもクイックソートの強みって、できるだけ均等に分割していくことによって比較回数を減らして高速化を図ることですよね？

ちなみに、
挿入ソートの平均計算計算量：O(n^2)
クイックソートの平均計算量:O(nlog n)
だと考えています

Answer 1

挿入ソートが一回の操作で要素を1つ正しい場所に置くことしかできない

違います。1回の操作で正しいところに置けるなら計算量はO(n)です。

挿入ソートの場合最後の一つを並べ替えるまで正しい場所は確定しません。
通常の配列を昇順にソートする場合を考えると、与えられた配列の最後の要素が最小要素の場合、その要素は先頭に挿入されるため、今まで並べた配列をすべて一つ後ろにずらす操作が発生します。
k番目の要素をソートしようとしたとき、挿入する位置は k/2 程度と期待されるので、k/2回の入れ替え操作が必要となります。
つまり
Σ(k=0,k<n) 1/2 × k =1/2×1/2×n(n-1) =1/4 n^2 -1/2 n
ランダウ記号では指数の最も大きい項のみ残すため、O(n^2)となります。

一方クイックソートでは、うまくピボットが選べていれば、1回の操作で要素の位置を半分まで特定できます。
つまり、一つの要素に対して、log n回の操作があればソートが完了します。つまり、n個の要素に対してO(n・log n)回程度の操作があればすべての要素がソートできるということです。

Comments

[zunda123]

返信ありがとうございます
あまり計算量などに詳しくない人にイメージを伝える場合、下記のテキストで問題ないでしょうか
「クイックソートは基本的に一回の操作で2つのグループに分けていくので、分割を行うたびに各グループの要素数が減り比較回数が減っていくので、挿入ソートよりはやくなることが多い」
スライドにどう書けばいいかいまいちよくわからなくて

[Kaleidoscope]

比較回数が減るから早くなるのではありません。交換回数が減るから早くなるのです。
ご自身でも理解されていないものを説明する、というのも難しい物があるかと思いますが。

言葉だけだと「早い」というイメージは伝わらないでしょう。
挿入ソートはn×nの正方形を左上から右下の対角線で切り、
左下半分がソート済み、対角線上がこれからソートする要素として、上から下へ処理が流れる図を出せばいいでしょう。O(n^2)がイメージできます。

クイックソートは長さnの横棒を1段づつ半分にしていく図を出して、高さがlog nと示せばO(n log n)のイメージがしやすいでしょう。

[Zuishin]

> 比較回数が減るから早くなるのではありません。交換回数が減るから早くなるのです。

比較回数で合ってるんじゃないでしょうか。

Answer 2

そもそもの認識が間違っていました

Answer 3

知らなかったので調べてみました。

挿入ソートが一回の操作で要素を1つ正しい場所に置くことしかできないのに対し、

ここ意味が分かりません。何が対比されているのですか?

クイックソートでは基本的に一回の操作で、グループを大きく二つに分けていくので分割を行うたびに要素数が減り比較回数が減っていく。

こちら違います。
グループを2つに分けたあと2つのグループ内でそれぞれ比較をするので要素数は減っていません。
分割したグループを階層に分けて
a, b,
aa, ab, ba, bb,
aaa, aab, aba, abb, baa, bab, bba, bbb,
...
と名付けたとして、
a, aa, aaaと進むと要素数は減っていきますが、同階層のグループ数は増えるので、結局1階層ごとの比較回数はO(n)で変わりません。

ポイントは階層数で、理想的には、2等分を繰り返すことになるので階層数はO(log n)になります。

一方挿入ソートでO(n^2)になる部分はどうやら2箇所あって、
・挿入回数がO(n)、1回の挿入ごとに挿入場所が見つかるまで順に舐めるので比較回数がO(n)、都合O(n^2)
・挿入回数がO(n)、1回の挿入ごとに挿入箇所以後を順にずらす処理がO(n)、都合O(n^2)
です。
後者はデータの持ち方をリンクリストにすることで解消できますが、前者に対処したものはどうやら2分挿入ソートという別のソート扱いになりそうです。