# ソート
速くなる
# 目的
「はんぶんこにしたら速くなる」ということだけ知っていればいいかなと思います。
バブルソートも挿入ソートの理解のポイントは 総当たりで比較している です。 総当たりで比較しています。そのため遅いです。
ヒープソートとクイックソートとマージソートの理解のポイントは、 半分にすると速くなる です。
細かくいろいろコードが書かれているのですが、 「はぶんこにしたら速くなる」、これだけ押さえていただければと思います。
# 実装
今回のソートのコードは以下にまとめさせていただきました。
また実装したアルゴリズムは以下のようになっています。
| アルゴリズム | 実装 | 途中 | ファイル |
|---|---|---|---|
| バブルソート | index | O | bubble.py |
| 挿入ソート | index | O | insertion.py |
| クイックソート | pop, append | X | linked_quick.py |
| クイックソート | index | O | quick.py |
| マージソート | pop, append | X | linked_merge.py |
| マージソート | index | O | merge.py |
| ヒープソート | pop, push | O | linked_heap.py |
| ヒープソート | index | X | heap.py |
原則的に添字表記 lst[index] の形式で実装しています。
末尾に linked がついているのは、
連結リスト (opens new window) を想定して pop, append で実装しています
（ヒープに関しては heappush, heappop になります）。
これだけだと何言ってるんだ？って感じですが、 詳細は各ページをご確認いただいた方がわかりやすいかなと思います。
# 途中
途中に o がついているファイルは途中結果を表示することができます。
実行のたびにランダムな数が生成されます。
表示の見方は各ページでご紹介させていただきます。
git clone https://github.com/niconico25/sort
cd sort
python3 bubble.py
$ python3 bubble.py
2 88 72 34 40
2 88 72 34 40
oo oo
2 88 72 34 40
xx xx
2 72 88 34 40
xx xx
2 72 34 88 40
xx xx
2 72 34 40 88
oo oo --
2 72 34 40 88
xx xx --
2 34 72 40 88
xx xx --
2 34 40 72 88
oo oo -- --
2 34 40 72 88
oo oo -- --
2 34 40 72 88
oo oo -- -- --
2 34 40 72 88
$
# 比較
10 ~ 100 個くらいならあまり変わらないのですが、 要素数が大きくなるにつれて劇的に ヒープソート, クイックソート, マージソートが速くなります。 これが「はんぶんこ」の圧倒的な威力です。
git clone https://github.com/niconico25/sort
cd sort
# 計測ツールのダウンロード
git clone https://github.com/niconico25/comparison_of_python_code
python3 -O comparison.py
$ python -O comparison.py
# 0 ~ 10 のランダムな整数を 10 個をソートさせます。
# Case 0
# [randint(0, 10**1) for i in range(0, 10**1)]
bubble_sort : 0.0140 [msec]
insertion_sort : 0.0131 [msec]
merge_sort : 0.0229 [msec]
heap_sort : 0.0240 [msec]
quick_sort : 0.0188 [msec]
linked_merge_sort : 0.0489 [msec]
linked_heap_sort : 0.0315 [msec]
linked_quick_sort : 0.0255 [msec]
# 0 ~ 100 のランダムな整数を 100 個をソートさせます。
# Case 1
# [randint(0, 10**2) for i in range(0, 10**2)]
bubble_sort : 1.1845 [msec]
insertion_sort : 0.9265 [msec]
merge_sort : 0.3418 [msec]
heap_sort : 0.3497 [msec]
quick_sort : 0.2707 [msec]
linked_merge_sort : 0.6628 [msec]
linked_heap_sort : 0.4223 [msec]
linked_quick_sort : 0.5004 [msec]
# 0 ~ 1000 のランダムな整数を 1000 個をソートさせます。
# Case 2
# [randint(0, 10**3) for i in range(0, 10**3)]
bubble_sort : 122.5598 [msec]
insertion_sort : 90.9587 [msec]
merge_sort : 5.0165 [msec]
heap_sort : 4.8568 [msec]
quick_sort : 3.6640 [msec]
linked_merge_sort : 8.1532 [msec]
linked_heap_sort : 5.3817 [msec]
linked_quick_sort : 6.1179 [msec]
$
ヒープソート、クイックソート、マージソートの中でも、 クイックソートが最も速いです。
バブルソートよりも挿入ソートが少しだけ速いというのも 心の片隅にうっすら抑えておいてください。
一般に添字表記 lst[index] の方が、
連結リスト想定 pop, append よりも速いです。
linked という接頭辞のついた連結リスト想定だと
ヒープソートが最速になっていますが、
標準ライブラリ heapq の実装が
添字表記 lst[index] になっているためです。
基本的には値に偏りがなければクイックソートが 最速という理解でいいかなと思います。
しかし細かいことはどうでもよくて、 総当たりをしているバブルソート、挿入ソートよりも、 基本的にはんぶんこにしている、 マージソート、ヒープソート、クイックソートが最も速いということ。
はんぶんこにすると圧倒的に速くなるということだけ、 押さえておいいただければと思います。
# TimSort
実際の Python のソートは TimSrot が使われている らしい です。 ソートのアルゴリズムは色々とあるのですが、 長短があるためそれを組み合わせて TimSort というものが作られているようです。
以下の記事では TimSort について解説してくれています。 ここでご紹介させていただく、挿入ソート、ヒープソート、クイックソート、マージソートの理解を前提にしています。
なのでここで書かれているアルゴリズムを何と無く把握すると 以下の記事も何と無く読めるようになるのではないかと考えています。 僕はまだ読めていません...
高速な安定ソートアルゴリズム TimSort の解説 (opens new window)
しかしながら、オリジナルのTimSortのコードは若干複雑で、 実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。
そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解説してみたいと思います ( クイックソート、マージソート、ヒープソート、挿入ソート の知識を前提とします)。
ちなみに TimSort の作者は PEP 20 (opens new window) の作者でもある Tim Peter 氏になります。
# 実装にあたって
ソートを実装するときは pdb (opens new window) を使うと便利です。