ソートアルゴリズムの説明を読んで「読んだだけでは覚えられないな、、」と思ったので、
代表的なアルゴリズム7種を実装し、実際に動かして性能を比較してみた
Pythonが書きやすそうな気がしたので、Pythonで書いた
目次
ソースコード
バブルソート
- 全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行う
- 一番シンプルなソート
| 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 |
|---|---|---|---|
| $n^{2}$ | $n^{2}$ | $1$ | あり |
def bubble_sort(lst):
n = len(lst)
for i in range(n):
for j in range(n-1):
if lst[j] >= lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
return lst
選択ソート
- 最も値の小さい要素を探し、それを1番目の要素と交換する（1番目の要素までソート済みとなる）
- 以降同様に、未ソート部分の最小要素を探し、未ソート部分の先頭要素と交換する
- すべての要素がソート済みになったら処理を終了する
| 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 |
|---|---|---|---|
| $n^{2}$ | $n^{2}$ | $1$ | なし |
def selection_sort(lst):
n = len(lst)
for i in range(0, n-1):
min = i
for j in range(i+1, n):
if lst[j] < lst[min]:
min = j
lst[i], lst[min] = lst[min], lst[i]
return lst
挿入ソート
- 0番目と1番目の要素を比較し、順番が逆であれば入れ換える
- 2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）
- 3番目以降の要素についても同様の処理を続け、全ての要素がソートされたら処理を終了する
| 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 |
|---|---|---|---|
| $n^{2}$ | $n^{2}$ | $1$ | あり |
def insertion_sort(lst):
for i in range(1, len(lst)):
tmp = lst[i]
j = i - 1
while j >= 0 and lst[j] > tmp:
lst[j+1] = lst[j]
j -= 1
lst[j+1] = tmp
return lst
シェルソート
- 適当な間隔 h を決める
- 間隔 h をあけて取り出したデータ列に挿入ソートを適用する
- 間隔 h を狭めて、再度データ列の抽出と挿入ソートを適用する、という処理をhが1になるまで続ける
| 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 |
|---|---|---|---|
| $n\log n$ | $\geqq n^{1.5}$ | $1$ | なし |
def shell_sort(lst):
n = len(lst)
h = 1
while h < n / 9:
h = h * 3 + 1
while h > 0:
for i in range(h, n):
j = i
while j >= h and lst[j-h] > lst[j]:
lst[j], lst[j-h] = lst[j-h], lst[j]
j -= h
h = h // 3
return lst
クイックソート
- ピボットという境界値を選択する
- ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する
- 分割された区間に対し、再びピボットの選択と分割を行う。この処理を分割区間が整列済みになるまで行う
- 最後に分割区間を統合する
| 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 |
|---|---|---|---|
| $n\log n$ | $n^2$ | $n\log n$ | なし |
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[0]
left = []
center = []
right = []
for v in lst:
if v < pivot:
left.append(v)
elif v > pivot:
right.append(v)
else:
center.append(v)
left = quick_sort(left)
right = quick_sort(right)
return left + center + right
ヒープソート
- 未整列のデータ列から要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し
- ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し
| 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 |
|---|---|---|---|
| $n\log n$ | $n\log n$ | $1$ | なし |
def heap_sort(lst):
n = len(lst)
for i in range(n//2-1, -1, -1):
heapify(lst, i, n)
for i in range(n-1, 0, -1):
lst[0], lst[i] = lst[i], lst[0]
heapify(lst, 0, i)
return lst
def heapify(lst, i, heap_size):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < heap_size and lst[left] > lst[largest]:
largest = left
if right < heap_size and lst[right] > lst[largest]:
largest = right
if largest != i:
lst[largest], lst[i] = lst[i], lst[largest]
heapify(lst, largest, heap_size)
マージソート
- データ列を分割する（通常、二等分する）
- 分割されたデータ列で、含まれるデータが1個ならそれを返し、2個以上なら、さらにデータ列の分割を行う
- 上記の再帰処理から返されたデータ列に対して、要素の比較による単純なソートを行う
- 二つのソートされたデータ列（1個であればそれ自身）をマージする
| 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 |
|---|---|---|---|
| $n\log n$ | $n\log n$ | $n$ | あり |
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = lst[:mid]
right = lst[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
merged = []
left_i, right_i = 0, 0
while left_i < len(left) and right_i < len(right):
if left[left_i] <= right[right_i]:
merged.append(left[left_i])
left_i += 1
else:
merged.append(right[right_i])
right_i += 1
if left_i < len(left):
merged.extend(left[left_i:])
if right_i < len(right):
merged.extend(right[right_i:])
return merged
実行時間を比較してみた
-100,000から100,000までの範囲から、ランダムに選ばれた数字100,000個を各アルゴリズムでソートしてみた
3つのデータセットに対してソートを行い、各回の所要時間と、平均所要時間を調べてみた
| アルゴリズム | 所要時間（秒） | 所要時間（秒） | 所要時間（秒） | 平均所要時間（秒） |
|---|---|---|---|---|
| バブルソート | 706.051 | 722.234 | 727.029 | 718.438 |
| 選択ソート | 200.039 | 204.399 | 200.981 | 201.806 |
| 挿入ソート | 203.928 | 202.049 | 203.315 | 203.097 |
| シェルソート | 0.516 | 0.517 | 0.557 | 0.530 |
| クイックソート | 0.146 | 0.132 | 0.139 | 0.139 |
| ヒープソート | 0.481 | 0.433 | 0.473 | 0.462 |
| マージソート | 0.287 | 0.271 | 0.279 | 0.279 |
やはり、基本的なソートである、バブル・選択・挿入と、高速化したソートであるシェル・クイック・ヒープ・マージとの間にはかなりの性能差がみられた
高速化したソートの中だと、クイックソートが一番速かった
（ただ、今回は割と安定したデータセットを使ったので、最悪計算量ベースでみたときに遅くなる可能性はある）
次点で、マージソートもそれなりに速かった
ちなみにソートする対象の個数ごとの所要時間は、以下の表のようになった
| アルゴリズム | 1,000 | 10,000 | 100,000 |
|---|---|---|---|
| バブルソート | 0.073 | 6.984 | 718.438 |
| 選択ソート | 0.019 | 1.976 | 201.806 |
| 挿入ソート | 0.020 | 2.046 | 203.097 |
| シェルソート | 0.002 | 0.030 | 0.530 |
| クイックソート | 0.001 | 0.012 | 0.139 |
| ヒープソート | 0.002 | 0.034 | 0.462 |
| マージソート | 0.002 | 0.023 | 0.279 |
やはり計算量が $O(n^{2})$ であるアルゴリズムは量が多くなるにつれて、かなり処理秒数が伸びているのに対し、
計算量が $O(nlogn)$ であるアルゴリズムは処理秒数の伸びを一定に留められている
おまけ
上記の実装から派生して、pythonが標準で提供しているsort関数が、
どのような実装になっているか気になったので、軽く調べてみた
どうやら、pythonのsort関数はティムソートというアルゴリズムを採用しているらしい
性能は以下とのこと
| 平均計算時間 | 最悪計算時間 | メモリ使用量 | 安定性 |
|---|---|---|---|
| $n\log n$ | $n\log n$ | $n$ | あり |
実際に動かしてみたら以下の実行時間となった
| アルゴリズム | 1,000 | 10,000 | 100,000 |
|---|---|---|---|
| ティムソート（python標準） | 0.000 | 0.001 | 0.013 |
かなり速い！（今回実装したクイックソートの10分の1ほどの速さでソートできるとは...）
さすが標準実装だな、という感じですね
理論上の性能からしても、最悪計算時間がクイックソートよりかなり速い（クイックソート：$O(n^{2})$, ティムソート：$O(nlogn)$ ）ので、メモリ使用量を気にしないのであれば、結構優秀なアルゴリズムな気がする
実装箇所はおそらく以下
頑張ればわかりそうだけど、（経験のない）C言語で書かれていてパッと読めるわけではなかったので、今回は断念...
（いつか、ティムソートの実装も理解したいが...）
ということで、この記事ではこれ以上深くは追わないので、
ティムソートについてより詳しく知りたい場合は、以下のページを読んでいただければ、と思います！
参考にしたページ