らんたくいっくそーと

数学ガール4巻を読んでいたら乱択クイックソートが出てきたのでPythonで書いてみた。本には疑似コードまで載せてあって読みやすい。

・普通のクイックソート

・乱択クイックソート

main()内でソートするリストの要素をrandint()で100万生成してそれをクイックソートする。一応最後にPythonに元からあるリストのソートと同じ結果になっているかの確認をする。比較のためにseed値を固定しておく。

実行結果がこちら。

・ふつうの

start
time: 9.663000
True

・乱択

start
time: 11.829000
True

乱択クイックソートの方が少し遅い。何回か繰り返してみたけど大体同じ感じだった。

次にソート済みのリストに対してソートをかけてみる。

c = range(9000)

c = range(9000, 0, -1)

として実行してみた結果がこちら。

ソース	クイックソート	乱択クイックソート
c = range(9000)	6.739000	0.071000
c = range(9000, 0, -1)	13.412000	0.074000
最初にやったやつ	9.663000	11.829000

だいたいこんな感じになった。
ソート済みのリストに対しては乱択クイックソートの方が圧倒的に速いことがわかる。
ソートする対象が、すでにソートされている部分があるかどうかわからないときは乱択クイックソートを使うのも良いかもと思った。