Sortアルゴリズムについて - Tech random memoranda

Bubbleソート、Quickソート、Mergeソート、をpythonとCで実装してみた。何年ぶりだろうか。なお、pythonはバグがあるので、Cを参照のこと。

Quickソートさえ分かっていればよくて、qsortとか標準ライブラリを使えば良いと思っていたけれど、Mergeソートに負けてしまった。最悪の計算量でいうと、QuickソートはO(n²)になってしまうが、MergeソートはO(n log n)で済む。ソート対象の配列が非常に大きい場合は、リスクを回避という観点で言えば、QuickソートよりMergeソートの方が良さそう。あとは、どのくらいソート対象の配列にランダム性があるのかどうか、という点も考える必要があるかもしれない。 pythonの方では、指定した数の倍のシーケンシャルなリストを作った後で、指定した数だけサンプリングし、その順序をランダマイズしたリストをソート対象としている。Cの方では、重複した値をテストするために、データをサンプリングする過程で100回に1回データの重複が発生するようにしている。

Cで試したところ、mergeソートの方がquickソートよりも常に速いが、あるデータサイズを超えると、quickソートの方が速くなる。というか、mergeソートがかなり遅くなる。これはおそらく、mergeソートの実装の方がメモリを消費するので、先に上限に達してしまうからだろう。mergeソートは必ず全ての要素を最小単位まで分割するため、quickソートよりもメモリの消費量は多い。（実装でうまく回避できるのかもしれないが）

ちなみに、メモリ量を最も抑えられるのはBubbleソートですね。必要なメモリは、ソート対象の配列と一つの変数だけ。スピードは非常に遅い（平均の計算量がO(n²)）けれど使用可能なメモリ量に厳しい制限があり、かつ、ソート対象の配列のサイズが小さいことが分かっていれば、Bubbleソートが解になりそうです。

Bubbleソート

import sys, random

i = int(sys.argv[1])
arr = list(range(i*2))
random.sample(arr,i)
rand_arr = list(arr)
random.shuffle(rand_arr)

def bs(arr):
    i=len(arr)
    while i>0:
        for j in range(0,i-1):
            if arr[j] > arr[j+1]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
        else:
            i -= 1
    return arr

sorted_arr = bs(rand_arr)
assert sorted_arr == arr

if not sorted_arr == arr:
    print(rand_arr)
    print(sorted_arr)

Quickソート

import sys,random

#arr = list(map(lambda x: int(x), sys.argv[1:]))

i = int(sys.argv[1])
arr = list(range(i*2))
random.sample(arr,i)
rand_arr = list(arr)
random.shuffle(rand_arr)

def qs(arr):
    #print(arr)

    if len(arr) == 1:
        return arr

    med = arr[0]
    #med = arr[int(len(arr)/2)]
    sg = list(filter(lambda x: x<med, arr))
    lg = list(filter(lambda x: x>med, arr)) 

    if len(sg) == 0:
        return [med]+qs(lg) 
    if len(lg) == 0:
        return qs(sg)+[med]

    return qs(sg)+[med]+qs(lg) 

sorted_arr = qs(rand_arr)
assert sorted_arr==arr

if not sorted_arr == arr:
    print(rand_arr)
    print(sorted_arr)

Mergeソート

import sys, random

i = int(sys.argv[1])
arr = list(range(i*2))
random.sample(arr,i)
random_arr = list(arr)
random.shuffle(random_arr)

#print(arr)
#print(random_arr)

def bs(arr):
    size = len(arr)
    if size == 1:
        return arr
    else:
        half = int(size/2)
        left_arr = bs(arr[:half])
        right_arr = bs(arr[half:])

        merged_arr = []
        left_idx = right_idx = 0
        while left_idx<half or right_idx<size-half:
            if left_idx == half:
                merged_arr.append(right_arr[right_idx])
                right_idx += 1
            elif right_idx == size-half:
                merged_arr.append(left_arr[left_idx])
                left_idx += 1
            elif left_arr[left_idx] < right_arr[right_idx]:
                merged_arr.append(left_arr[left_idx])
                left_idx += 1
            elif left_arr[left_idx] >= right_arr[right_idx]:
                merged_arr.append(right_arr[right_idx])
                right_idx += 1

        return merged_arr

sorted_arr = bs(random_arr)
#print(sorted_arr)

assert sorted_arr == arr

if not sorted_arr == arr:
    print(arr)
    print(sorted_arr)

Python実装のLinux上での実行結果

$ time python bubblesort.py 5000

real    0m10.906s
user    0m10.831s
sys 0m0.053s

$ for i in $(seq 1 3); do time python mergesort.py 1000000; done

real    0m26.053s
user    0m24.332s
sys 0m0.363s

real    0m26.276s
user    0m25.174s
sys 0m0.375s

real    0m23.590s
user    0m23.303s
sys 0m0.220s

$ for i in $(seq 1 3); do time python quicksort.py 1000000; done

real    0m28.814s
user    0m28.425s
sys 0m0.341s

real    0m26.910s
user    0m26.567s
sys 0m0.311s

real    0m28.079s
user    0m27.733s
sys 0m0.325s

C実装

Run sort algorithms with randomized single data · GitHub

C実装のMacでの実行結果

$ ./sort 10000000
Quick sort : 13.00 sec.
Sorted check OK.
Merge sort : 9.92 sec.
Sorted check OK.

$ ./sort 20000000
Quick sort : 21.84 sec.
Sorted check OK.
Merge sort : 16.55 sec.
Sorted check OK.

$ ./sort 50000000
Quick sort : 78.04 sec.
Sorted check OK.
Merge sort : 201.94 sec.
Sorted check OK.