質問: 情報系の学生です。 クイックソートが挿入ソートよりも一般的にはやい理由の説明について質問があります。(クイックソートが遅くなることもありますが今回は考えません) 今度、挿入ソートよりクイックソートのほうが一般的に早い理由を説明する機会があります。 そこで、今現在考えているのが 「挿入ソートが一回の操作で要素を1つ正しい場所に置くことしかできないのに対し、クイックソートでは基本的に一回の操作で、グループを大きく二つに分けていくので分割を行うたびに要素数が減り比較回数が減っていく。結果として挿入ソートより早くなることが多い」 という説明で間違いはないでしょうか そもそもクイックソートの強みって、できるだけ均等に分割していくことによって比較回数を減らして高速化を図ることですよね? ちなみに、 挿入ソートの平均計算計算量:O(n^2) クイックソートの平均計算量:O(nlog n) だと考えています
回答: >挿入ソートが一回の操作で要素を1つ正しい場所に置くことしかできない 違います。1回の操作で正しいところに置けるなら計算量はO(n)です。 挿入ソートの場合最後の一つを並べ替えるまで正しい場所は確定しません。 通常の配列を昇順にソートする場合を考えると、与えられた配列の最後の要素が最小要素の場合、その要素は先頭に挿入されるため、今まで並べた配列をすべて一つ後ろにずらす操作が発生します。 k番目の要素をソートしようとしたとき、挿入する位置は k/2 程度と期待されるので、k/2回の入れ替え操作が必要となります。 つまり `Σ(k=0,k