Pythonで7種のソートを実装して、性能を比較してみた

ソートアルゴリズムの説明を読んで「読んだだけでは覚えられないな、、」と思ったので、
代表的なアルゴリズム7種を実装し、実際に動かして性能を比較してみた
Pythonが書きやすそうな気がしたので、Pythonで書いた

# 目次
- [ソースコード](#ソースコード)
- 各アルゴリズムの実装
    - [バブルソート](#バブルソート)
    - [選択ソート](#選択ソート)
    - [挿入ソート](#挿入ソート)
    - [シェルソート](#シェルソート)
    - [クイックソート](#クイックソート)
    - [ヒープソート](#ヒープソート)
    - [マージソート](#マージソート)
- 性能比較
    - [実行時間を比較してみた](#実行時間を比較してみた)
- [おまけ](#おまけ)
- [参考にしたページ](#参考にしたページ)

# ソースコード
https://github.com/Kaito-Ozaki/sort-algorithm

# [バブルソート](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88)
- 全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行う
- 一番シンプルなソート

|平均計算時間|最悪計算時間|メモリ使用量|安定性|
|---|---|---|---|
|$n^{2}$|$n^{2}$|$1$  |あり|

```python
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
```

# [選択ソート](https://ja.wikipedia.org/wiki/%E9%81%B8%E6%8A%9E%E3%82%BD%E3%83%BC%E3%83%88)
- 最も値の小さい要素を探し、それを1番目の要素と交換する（1番目の要素までソート済みとなる）
- 以降同様に、未ソート部分の最小要素を探し、未ソート部分の先頭要素と交換する
- すべての要素がソート済みになったら処理を終了する

|平均計算時間|最悪計算時間|メモリ使用量|安定性|
|---|---|---|---|
|$n^{2}$|$n^{2}$|$1$  |なし|

```python
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
```

# [挿入ソート](https://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88)
- 0番目と1番目の要素を比較し、順番が逆であれば入れ換える
- 2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」する（配列の場合、前の要素を後ろに一つずつずらす）
- 3番目以降の要素についても同様の処理を続け、全ての要素がソートされたら処理を終了する

|平均計算時間|最悪計算時間|メモリ使用量|安定性|
|---|---|---|---|
|$n^{2}$|$n^{2}$|$1$  |あり|

```python
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
```

# [シェルソート](https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88)
- 適当な間隔 h を決める
- 間隔 h をあけて取り出したデータ列に挿入ソートを適用する
- 間隔 h を狭めて、再度データ列の抽出と挿入ソートを適用する、という処理をhが1になるまで続ける

|平均計算時間|最悪計算時間|メモリ使用量|安定性|
|---|---|---|---|
|$n\log n$|$\geqq n^{1.5}$|$1$  |なし|

```python
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
```

# [クイックソート](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88)
- ピボットという境界値を選択する
- ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する
- 分割された区間に対し、再びピボットの選択と分割を行う。この処理を分割区間が整列済みになるまで行う
- 最後に分割区間を統合する

|平均計算時間|最悪計算時間|メモリ使用量|安定性|
|---|---|---|---|
|$n\log n$|$n^2$|$n\log n$  |なし|

```python
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
```

# [ヒープソート](https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88)
- 未整列のデータ列から要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し
- ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し

|平均計算時間|最悪計算時間|メモリ使用量|安定性|
|---|---|---|---|
|$n\log n$|$n\log n$|$1$  |なし|

```python
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)
```

# [マージソート](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88)
- データ列を分割する（通常、二等分する）
- 分割されたデータ列で、含まれるデータが1個ならそれを返し、2個以上なら、さらにデータ列の分割を行う
- 上記の再帰処理から返されたデータ列に対して、要素の比較による単純なソートを行う
- 二つのソートされたデータ列（1個であればそれ自身）をマージする

|平均計算時間|最悪計算時間|メモリ使用量|安定性|
|---|---|---|---|
|$n\log n$|$n\log n$|$n$  |あり|

```python
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関数が、
どのような実装になっているか気になったので、軽く調べてみた

https://docs.python.org/ja/3/howto/sorting.html#sort-stability-and-complex-sorts

どうやら、pythonのsort関数は[ティムソート](https://ja.wikipedia.org/wiki/%E3%83%86%E3%82%A3%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88)というアルゴリズムを採用しているらしい

性能は以下とのこと

|平均計算時間|最悪計算時間|メモリ使用量|安定性|
|---|---|---|---|
|$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)$ ）ので、メモリ使用量を気にしないのであれば、結構優秀なアルゴリズムな気がする

実装箇所はおそらく以下

https://github.com/python/cpython/blob/main/Objects/listobject.c#L2522

頑張ればわかりそうだけど、（経験のない）C言語で書かれていてパッと読めるわけではなかったので、今回は断念...
（いつか、ティムソートの実装も理解したいが...）

ということで、この記事ではこれ以上深くは追わないので、
ティムソートについてより詳しく知りたい場合は、以下のページを読んでいただければ、と思います！

https://qiita.com/nishiwakki/items/806c24b8d061083d0808

https://qiita.com/tomocat/items/7905ec4370c852f8d19d


# 参考にしたページ
https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88

https://qiita.com/suecharo/items/30f5d817da4c948c3be6

https://engineeringnote.hateblo.jp/entry/python/algorithm-and-data-structures/shell_sort

https://watlab-blog.com/2022/03/13/quick-sort/

https://hawk-tech-blog.com/python-algorithm-sort-heap-sort/