はじめに

いくつかのソートアルゴリズムについてまとめてみました。

それぞれのポイントと Python での実装例、それぞれの速度の計測について記述しました。

なるべく組み込み関数を使わないように実装したため、あまり速度は出ませんが、sort() や sorted() より早いものを出来たらなと考えてました。

扱うソートアルゴリズム

扱うソートアルゴリズムは、

バブルソート (bubble sort)
選択ソート (select sort)
挿入ソート (insert sort)
マージソート (merge sort)
クイックソート (quick sort)
カウントソート (count sort)

名称	平均計算時間	最悪計算時間	メモリ使用量	安定性
バブルソート	$O(n^2)$	$O(n^2)$	$O(1)$	安定
選択ソート	$O(n^2)$	$O(n^2)$	$O(1)$	安定ではない
挿入ソート	$O(n^2)$	$O(n^2)$	$O(1)$	安定
マージソート	$O(n\log n)$	$O(n\log n)$	$O(n)$	安定
クイックソート	$O(n\log n)$	$O(n^2)$	$O(\log n)$	安定ではない
カウントソート	$O(nk)$	$O(n^2 k)$	$O(nk)$	安定ではない

他にも有名なソートアルゴリズムとしてヒープソート・シェルソート・基数ソートがありますが今回は見送りました。いずれ追加していきたいです。

ヒープソートとかだと、Python の heapq モジュールを使えば実装がかなり楽ですが、それって sort() やるのと何が違うのって感じになります、、

安定性とは、例えば [1-b, 2-a, 1-a, 2-b] みたいなデータを数字をキーとしてソートした際、ソート前の順番が保存されていて、[1-b, 1-a, 2-a, 2-b] となるようなものを安定であると定義していると認識しています。

それぞれのポイントと実装

バブルソート

横同士の大小を比較交換をし、更にそれを変更の必要がなくなるまで行う。
シンプルでわかりやすい。

bubble_sort.py

def bubble_sort(arr):
    change = True
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
    return arr

選択ソート

配列中の最小か最大を選択し、それを端に移動させていく。
シンプルでわかりやすい。

min() は使ってよいのかって感じはあります、、

メモリ使用量を $O(1)$ にするために、新しい list に入れていくのではなく置換で実装しています。

sellect_sort.py

def sellect_sort(arr):
    for ind, ele in enumerate(arr):
        min_ind = min(range(ind, len(arr)), key=arr.__getitem__)
        arr[ind], arr[min_ind] = arr[min_ind], ele
    return arr

挿入ソート

左から順に、整列してある配列の適当な部分に挿入していく。
挿入する場所を探す際、2分探索を用いることで高速化出来る。
マージソートやクイックソートに比べ、データの状態に依存しない。
ほとんどソート済みの配列や、比較的小さな配列に対して強い。
シンプルでわかりやすい。

2分探索を用いない場合は、

insert_sort.py

def insert_sort(arr):
    for i in range(1, len(arr)):
        j = i - 1
        ele = arr[i]
        while arr[j] > ele and j >= 0:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = ele
    return arr

2分探索を用いる場合は、

insert_sort_bin.py

import sys
sys.setrecursionlimit(10 ** 7)

def binary_search(arr, low, hig, ele):
    if low == hig:
        if arr[low] > ele:
            return low
        else:
            return low + 1
    elif low > hig:
        return low

    mid = (low + hig) // 2
    if arr[mid] < ele:
        return binary_search(arr, mid + 1, hig, ele)
    elif arr[mid] > ele:
        return binary_search(arr, low, mid - 1, ele)
    else:
        return mid

def insert_sort_bin(arr):
    for i in range(1, len(arr)):
        ele = arr[i]
        ind = binary_search(arr, 0, i - 1, ele)
        arr[:] = arr[:ind] + [ele] + arr[ind:i] + arr[i + 1:]
    return arr

ちなみに、2分探索用のモジュールである bisect を用いる場合は、

insert_sort_bin_buildin.py

import bisect
def insert_sort_bin_buildin(arr):
    for i in range(1, len(arr)):
        bisect.insort(arr, arr.pop(i), 0, i)
    return arr

マージソート

最初に分割を繰り返し、その後順に結合していく。
結果としては、分割と結合が再帰的に行われる。
結合する過程でソートされていく。
ソートされた配列同士の結合のため、結合の仕方を工夫する。
結合にheapqのmergeを用いることも出来る。
ある程度まで分割できたら、別のソートアルゴリズムを用いることで高速化出来る。
かなり早いがメモリを多く使う。
並列で処理が可能

merge_sort.py

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

クイックソート

基準値を決めて、その基準値から見て大小の2つの配列に分ける。
この基準値の選び方として、配列の最初や最後、適当な3つぐらいの値の中央値などを用いる。
分けたグループの中で、更に再帰的に同じ処理を行っていく。
基準値の決め方に性能が左右される。
ある程度まで分割できたら、別のソートアルゴリズムを用いることで高速化出来る。
かなり早いがメモリを多く使う。
安定なソートではない。

quick_sort.py

def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # データの状態に左右されないためにrandom.choice()を用いることもある。
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

カウントソート

それぞれの値の個数を数えていく。
実装が簡単。
値の範囲によってはかなり高速。

カウントソートによく似たソートアルゴリズムとして、バケットソートが挙げられます。バケットソートはある程度の範囲を持った箱をいくつか作り、そこに値を入れていき、箱ごとにソートしたあと結合するというソートアルゴリズムみたいです。

カウントソートもそれぞれの値ごとの箱を作り、そこに追加していけば安定性が保たれますが、考え方が count というより bucket になるためこのような実装となりました。collections.defaultdict モジュールとか使えば、かなり実装が楽で安定性がある実装ができると思います。

count_sort.py

def count_sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    count = [0] * (max_num - min_num + 1)
    for ele in arr:
        count[ele - min_num] += 1

    return [ele for ele, cnt in enumerate(count, start=min_num) for __ in range(cnt)]

速度比較

用いるデータセット

numpy.random で生成した。

作成したデータセットは、

data1：0-100 の範囲での整数の一様乱数 100 個
data2：0-1000 の範囲での整数の一様乱数 10000 個
data3：0-100 の範囲での整数の一様乱数 10000 個
data4：平均 10 、標準偏差 5 の標準正規分布の乱数 100 個
data5：平均 100 、標準偏差 50 の範囲での標準正規分布の乱数 10000 個
data6：0-100 の範囲での整数の一様乱数 100 個で既に逆順でソートされているもの
data7：0-100 の範囲での整数の一様乱数 100 個で既にソートされており、最初の 10 個だけ順番がぐちゃぐちゃになったもの

make_data.py

data_rand_1 = list(randint(0, 10 ** 2, 10 ** 2))
data_rand_2 = list(randint(0, 10 ** 4, 10 ** 4))
data_rand_3 = list(randint(0, 10 ** 2, 10 ** 4))
data_rand_4 = [int(normal(10, 5)) for __ in range(10 ** 2)]
data_rand_5 = [int(normal(10 ** 2, 50)) for __ in range(10 ** 4)]
data_rand_6 = sorted(randint(0, 10 ** 2, 10 ** 2), reverse=True)
data_rand_7 = sorted(randint(0, 10 ** 2, 10 ** 2))
data_rand_7[0: 10] = choice(data_rand_7[0: 10], 10, replace=False)

速度の計測

下記コードを利用して 100 回測定し、その平均を求めた。Jupyter notebook の timeit コマンドではうまく測れなかった。

単位は、μs である。

なるべく誤差を減らすためにそれぞれのアルゴリズムごとに計測を行った。多分、CPU とかメモリの仕様にもよると思うが、ループを使って全部のアルゴリズムをいっぺんに測定できるような実装にしたら、極端に性能が落ちるものがあった。

time.py

datas = [data_rand_1, data_rand_2, data_rand_3,
             data_rand_4, data_rand_5, data_rand_6, data_rand_7]

for ind, data in enumerate(datas):
    print("---- DataSet : {0} ----".format(ind + 1))
    times = []
    for i in range(100):
        start = time.time()
        # 計測したいソートアルゴリズム
        sorted(data)
        elapsed_time = int((time.time() - start) * (10 ** 6))
        times.append(elapsed_time)

    print(sum(times) // 100)

種類	一様乱数	大きい一様乱数	狭くて大きい一様乱数	正規分布	大きい正規分布	逆順のソート済み	ほとんどソート済み
Python 組み込みソート	16	3488	2938	10	2447	12	6
バブルソート	25	167789	163781	21	154426	26	10
選択ソート	418	4025181	3889431	379	3552541	433	422
挿入ソート	24	58281	53705	19	47764	25	17
挿入ソート (2分探索)	627	1382480	1338027	334	1278530	347	339
マージソート	593	67221	61657	329	59483	270	233
クイックソート	142	25911	12009	56	12044	469	542
カウントソート	95	5597	2164	24	1607	57	51

とりあえず結果の考察

Python の組み込みソートは早い。
低級なソートの中では挿入ソートが比較的早い。
挿入ソートで2分探索しても早くならない。
マージソートとクイックソートが予想に反して遅い。もっと大きなデータで、クイックソートの途中でカウントソートを挟めばかなり早くなると思う。
殆どのアルゴリズムはデータの状態によって結果が悪くならないが、クイックソートだけデータの状態によっては性能が落ちる。

組み込みソートより早いアルゴリズムを求めて

狭い範囲の場合は、カウントソートを用いれば組み込みソートより早くなるようだ。

カウントソートの親戚であるバケットソートとかをうまく実装できたらより早いアルゴリズムを組めるのではないかと思う。

とりあえず、クイックソートとカウントソートを組み合わせて、大きな量のデータを入れてみる。

用意したデータは、big_data = list(randint(0, 10 ** 3, 10 ** 6)) である。

quick_sort_with_count.py

def quick_sort_with_count(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    ref = choice(arr)
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1

    if len(left) <= 1000:
        left = count_sort(left)
    else:
        left = quick_sort_with_count(left)

   if len(right) <= 1000:
        right = count_sort(right)
    else:
        right = quick_sort_with_count(right)

    return left + [ref] * ref_count + right

種類	結果
Python 組み込みソート	464109
クイックソート	2069006
カウントソート	250043
クイックソート + カウントソート	3479010

結論として

とりあえず時間が尽きたのでここまでです。時間があれば、細かい刻みのデータセットを用意して Python の組み込みソートとカウントソートを比較検証してみます。

マージソート・クイックソート等は一般的に早いと言われていますが、とりあえず Python では再帰呼び出しなどに時間がかかるため、あまり早くないようです。

値の範囲や種類がわかっている場合は、カウントソートが有用であると考えられます。日本語の Wikipedia は記事すら存在せず、英語のドキュメントはバケットソートと混同しているものをちらほら見かけますが、、、

参考ページ

Wikipedia ソート : ソートアルゴリズムについて網羅的に書いてある。
Rosetta Code : それぞれのアルゴリズムの言語別に集めた実装例集。ここらへんから落とし込んでみた。
Numpyによる乱数生成まとめ
処理にかかる時間を計測して表示

ソートアルゴリズムと Python での実装