Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

はじめに

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

それぞれのポイントと 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)

Unknown.png

Unknown-1.png

Unknown-2.png

Unknown-3.png

Unknown-4.png

Unknown-5.png

Unknown-6.png

速度の計測

下記コードを利用して 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 は記事すら存在せず、英語のドキュメントはバケットソートと混同しているものをちらほら見かけますが、、、

参考ページ

suecharo
The University of Tokyo UI-Lab, RIKEN AIP Search and Parallel Unit, Rhelixa, Inc. Senior Researcher of Cloud Dev., Ascade, Inc. Software Engineer of System Solution Div.
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした