ソート~アルゴリズムのHello World!

けったん（エンジニア）

2024.02.15

IT技術

アルゴリズムクイックソートシェルソートバブルソートマージソート

はじめに

こんにちは。
「ソート」はどの言語においても標準ライブラリなどで高速のアルゴリズムが採用されています。わざわざ実装する機会はなかなかないかと思います。一方でソートのアルゴリズムはアルゴリズム界のHello Worldと言っていいくらい重要です。（素晴らしい記事の受け売りです）
今回はみなさん大好きなソートアルゴリズムについて書こうと思います。
「バブルソート」、「シェルソート」、「マージソート」、「クイックソート」について、そのアルゴリズムと動作をわかりやすく説明することを重視しました（時間計算量や、空間計算量は深入りしません）。
いきなりアルゴリズムのお話ではつかれてしまうので、まずはイメージをつかんでいこうと思います。

質問

条件
- ・同時に比較できるのは２人までとします。
- ・自分で動くのがめんどくさいらしく、あなたが移動してください。

みなさんならどうします？
ここには「sort」メソッドが存在しません。何回も移動させるのは時間がかかってしまいます。なるべく少ない回数で移動させたいです。
そんな状況でソートアルゴリズムを一緒に眺めていきましょう。

バブルソート

まずはバブルソートについて説明していきます。
その名前のように、泡が上に登っていく様子がソートの状態を表しているので名前がついたようです。

直感的にわかりやすいアルゴリズムになります。
誕生日が遅い人（最初は最初の人）がいたらその人を基準にします。比較対象の人が基準の人より遅かったら、その人を基準にして今までの基準の人をそこに入れます。
最後まで行くと一番遅い人が最後にきます。

左から順番に次のものと比較していく。大きかったら順番を入れ替える
一度右まで行くと一番右に一番大きなものが配置される
一番右は「整列済」となるので、次のターンではその一つ前まで比較する
上記を繰り返す

一番最初に検索する際には全てを比較し、だんだんと比較数が少なくなります。
これが大事で「はし」から「はし」までを毎回調べていると時間がかかってしまいます。
一方で最後は検索範囲がせまくなるので高速です。少ないサンプルでは有効なアルゴリズムです。

・内部ソート（与えられた配列内でソートをしていくので新たに追加のメモリを使用しない）
・安定ソート（同じ値を持つ要素がもともと持っていた相対的な順序をソート後も保持する）
・時間計算量 O(n^2)　遅い

などの特徴があります。pythonで実装すると以下のようになります。

1import random as rand
2
3rand.seed(0)
4n = 100
5ar = rand.sample(range(1,n+1),n)
6
7# 昇順にならべる（一番大きいものを右へ
8def bubble_sort(ar, n):
9    for i in range(n-1, 0, -1):
10        for j in range(0, i):
11            if ar[j] > ar[j+1]:
12                temp = ar[j]
13                ar[j] = ar[j+1]
14                ar[j+1] = temp
15
16result = []
17bubble_sort(ar, n)
18print(ar)

シェルソート

次はシェルソートについて説明していきます。
シェルソートは挿入ソートの思想を引き継いで高速化したものですが、イメージがつきにくいかと思います。
挿入ソートは基本的なソート方法で、すべての配列を順番に取り出して適切な位置にならべていくアルゴリズムです。（列の一番左の人をまずは左に並べる。次の人は並べた配列の左の人から順番に調べていき適切なところに並べる=挿入する。）
挿入ソートの欠点としてはランダムさが大きい場合には遅くなるという欠点があります。そのためシェルソートでは、部分列に対して挿入ソートをする。というイメージです。

色々な所で最初はソートが行われます。
これはh（以下のコード参照）により決められた幅の要素のみに着目し、あらかじめざっと整列を行います。
最後にはh=1で挿入ソートを行って、順番を決定します。

Hで指定されたh（着目する幅）の部分のみに着目します
上記を挿入ソートします
hを小さく（Hで指定されている）して繰り返します

ある程度整列をしておくことで挿入ソートの効率を高めています。

・内部ソート（与えられた配列内でソートをしていくので新たに追加のメモリを使用しない）
・安定ソートではない（同じ値を持つ要素がもともと持っていた相対的な順序をソート後も保持しない）
・(..., 364, 121, 40, 13, 4, 1) を間隔列として採用すると、平均時間計算量 O(n^1.25)　になるらしいので今回は(40, 13, 4, 1)で指定しています

hの幅をどのように決定するかはまだわからない未解決問題であり、今後も改善されていきそうです。h_i+1=3h_i+1を満たす整数列のみ平均時間計算量が上記になるようです。

1import random as rand
2
3rand.seed(0)
4ar = rand.sample(range(1,101),k=100)
5
6def insertion_sort(ar, n, h):
7    for i in range(h, n):
8        x = ar[i]
9        j = i - h
10
11        while j >= 0 and ar[j] > x:
12            ar[j+h] = ar[j]
13            j -= h       
14        ar[j+h] = x
15
16def shell_sort(ar, n, H):
17    for h in H:
18        insertion_sort(ar, n, h)
19
20H = [40, 13, 4, 1]
21shell_sort(ar, 100, H)
22print(ar)

マージソート

次はマージソートについて説明していきます。
これはアルゴリズムが直感的にはわかりにくいのですが、gif画像を見ていただければ理解しやすいかと思います。

部分的にソートが行われ、ソートがどんどんマージしていきます。
一番アニメーション化して良かったと思うアルゴリズムですw

配列を要素数1or2になるまで２等分していきます
配列同士をマージするときに先頭から比較してならべていきます
上記を再帰的に繰り返します

細かく分割（分割統治法）し、再帰的に処理することで整列していきます。
配列を新規で作成するので追加のメモリが必要です。

・外部ソート（新たに追加のメモリを使用する）
・安定ソート（同じ値を持つ要素がもともと持っていた相対的な順序をソート後も保持する）
・時間計算量 O(n*log(n)) そこそこ早い

1import random as rand
2
3rand.seed(0)
4ar = rand.sample(range(1,101),k=100)
5
6def merge(ar, left, mid, right): 
7    left_ar = ar[left:mid]
8    right_ar = ar[mid:right]
9    left_len = len(left_ar)
10    right_len = len(right_ar)
11    
12    # 左右の比較対象のindex
13    left_index = 0
14    right_index = 0
15
16    for i in range(left, right):
17        if (left_index < left_len) and (right_index < right_len):
18            if left_ar[left_index] < right_ar[right_index]:
19                ar[i] = left_ar[left_index]
20                left_index += 1
21            else:
22                ar[i] = right_ar[right_index]
23                right_index += 1
24        elif left_index == left_len:
25            ar[i:right] = right_ar[right_index:]
26            return
27        else:
28            ar[i:right] = left_ar[left_index:]
29            return
30
31def merge_sort(ar, left, right):
32    if right - left > 1:
33        mid = (left + right)//2
34        merge_sort(ar, left, mid)
35        merge_sort(ar, mid, right)
36        merge(ar, left, mid, right)
37
38merge_sort(ar, 0, 100)
39print(ar)

クイックソート

次はクイックソートについて説明していきます。
これはマージソートと逆でアルゴリズムの方が直感的にはわかりやすく、gif画像を見てもわかりにくいと思います。

あるpivot（基準の要素）を元に、後ろと前に配列を入れ替えていくアルゴリズムです。
今回は配列の最後をpivotに指定しています。

pivotを基準に値の大小を左右に配置していく
上記を再帰的に繰り返します

その名の通りクイックなソートです。
pivotをどのような値にするかが大事になります（ランダムに選んだ3要素の中央値など）。

・内部ソート（与えられた配列内でソートをしていくので新たに追加のメモリを使用しない）
・安定ソートでない（同じ値を持つ要素がもともと持っていた相対的な順序をソート後も保持しない）
・時間計算量 O(n*log(n)) 多くの場合高速

1import random as rand
2
3rand.seed(0)
4ar = rand.sample(range(1,101),k=100)
5
6# 配列の最後の値をpivotとする
7def quick_sort(ar, left, right):
8    if right - left < 2:
9        return
10    
11    pivot = ar[right-1]
12    search_index = left
13    
14    for i in range(left, right):
15        if ar[i] < pivot:
16            temp = ar[i]
17            ar[i] = ar[search_index]
18            ar[search_index] = temp
19            search_index += 1
20    temp = ar[search_index]
21    ar[search_index] = pivot
22    ar[right-1] = temp
23    
24    quick_sort(ar, left, search_index)
25    quick_sort(ar, search_index+1, right)
26
27quick_sort(ar, 0, 100)
28print(ar)

おまけ

今回はjupyterを使用したかったのでpythonで実装しました。
matplotlibでgif画像の生成しましたので、そのコードも参考に載せておきます。

1#-------------------------------------------------
2# バブルソートの場合
3import random as rand
4import copy
5
6rand.seed(0)
7n = 50
8ar = rand.sample(range(1,n+1),n)
9
10result = []
11result = bubble_sort(ar, n, result)
12
13# 昇順にならべる（一番大きいものを右へ
14def bubble_sort(ar, n, result):
15    for i in range(n-1, 0, -1):
16        for j in range(0, i):
17            if ar[j] > ar[j+1]:
18                temp = ar[j]
19                ar[j] = ar[j+1]
20                ar[j+1] = temp
21                result.append(copy.copy(ar))
22    return result
23#-------------------------------------------------
24# 画像生成部分
25
26import itertools
27import matplotlib.pyplot as plt
28from matplotlib import animation
29from IPython.display import HTML
30
31fig = plt.figure(figsize=(10, 6))
32
33ims = []
34
35# gifのframeをrepeat前に追加（最後のframe追加）
36[result.append(result[-1]) for i in range(50)]
37
38for idx, res in enumerate(result):
39    # 条件に基づいて色を指定
40    colors = ['blue' if last == before else 'red' for last, before in zip(res, result[idx-1])]
41    im = plt.bar(np.arange(1,n+1), res, color=colors)
42    ims.append(im)
43
44ani = animation.ArtistAnimation(fig, ims, interval=80)
45
46# グラフを保存する
47ani.save('bubble_sort.gif', writer='pillow')
48
49# 上記をコメントアウトして下記を外すとブラウザに操作バーが表示されて便利
50# HTML(ani.to_jshtml())