Math Battle [ 0325: 最悪ケースでの sort 比較 ]

[ 0325: 最悪ケースでの sort 比較 ]

[ 広世正憲の回答 ]

乗児君がお膳立てしてくれましたので、
それを引き継いで最悪ケース (worst case) での実行時間を比較してみました。
最悪ケースとは対象となる配列のデータが逆順に並んでいる場合です。

データがランダムに並んでいる場合は QuickSort と MergeSort はほぼ変わらず。
HeapSort は速いです。
Worst case になると QuickSort は非常に遅くなります。途中でやめました。
MergeSort と HeapSort はデータのランダムさに影響を受けていません。

[ 湯会老人のコメント ]

正憲君、お疲れさま。

われわれは QuickSort が最も速いと思っていましたが、
実は HeapSort のほうが安定して速いわけですね。
なお、QuickSort の中で pivot を決める部分がありますが、
この部分を乱数を使うなどして改造すれば
worst case での性能が良くなるかも知れません。

他のメンバーからのコメントを待ちましょう。

[ 井伊莞爾君のコメント ]

C/C++ では stdlib.h で宣言された qsort (quick sort) が使えますね。
Perl 組み込みの sort 関数はどのアルゴリズムを使っているのでしょうか？

[ 三方万理先生のコメント ]

莞爾君、Perl の sort は今は MergeSort です。

Perl 5.6 and earlier used a quicksort algorithm ...
In 5.7, the quicksort implementation was replaced with a
stable mergesort algorithm.

QuickSort は worst case では O (n^2) になります。
欠点はスピードだけではありません。
複合ソートでは結果がグシャグシャになります。

[ 大宙麗亜ちゃんのコメント ]

私はまだ Perl で sort を使ったことがありませんが、
安心して使っていいわけですね。Sort を使う問題を出してください。