Sortアルゴリズムについて
Bubbleソート、Quickソート、Mergeソート、をpythonとCで実装してみた。何年ぶりだろうか。なお、pythonはバグがあるので、Cを参照のこと。
Quickソートさえ分かっていればよくて、qsortとか標準ライブラリを使えば良いと思っていたけれど、Mergeソートに負けてしまった。 最悪の計算量でいうと、QuickソートはO(n2)になってしまうが、MergeソートはO(n log n)で済む。 ソート対象の配列が非常に大きい場合は、リスクを回避という観点で言えば、QuickソートよりMergeソートの方が良さそう。あとは、どのくらいソート対象の配列にランダム性があるのかどうか、という点も考える必要があるかもしれない。 pythonの方では、指定した数の倍のシーケンシャルなリストを作った後で、指定した数だけサンプリングし、その順序をランダマイズしたリストをソート対象としている。Cの方では、重複した値をテストするために、データをサンプリングする過程で100回に1回データの重複が発生するようにしている。
Cで試したところ、mergeソートの方がquickソートよりも常に速いが、あるデータサイズを超えると、quickソートの方が速くなる。というか、mergeソートがかなり遅くなる。これはおそらく、mergeソートの実装の方がメモリを消費するので、先に上限に達してしまうからだろう。mergeソートは必ず全ての要素を最小単位まで分割するため、quickソートよりもメモリの消費量は多い。(実装でうまく回避できるのかもしれないが)
ちなみに、メモリ量を最も抑えられるのはBubbleソートですね。必要なメモリは、ソート対象の配列と一つの変数だけ。スピードは非常に遅い(平均の計算量がO(n2))けれど使用可能なメモリ量に厳しい制限があり、かつ、ソート対象の配列のサイズが小さいことが分かっていれば、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)
$ 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.