こんばんは。今日は、ソートアルゴリズムについて学んだことを整理しておきたいと思います。
最近はReact Native, Azureの話が多かったのですが、今日はもう少し理論的なお話になります。
それではまいります。
Contents
クイックソートの概要
- 1960年にイギリスの計算機科学者、アントニー・ホーアによって発明されたソートアルゴリズム
- 分割統治法の一種
- n個のデータをソートする際の最良計算量および平均計算量はnlognのオーダー（底は2、だそう）
- 最悪の計算量はnの2乗
- クイックソートの性能は、基準値（以下手順参照）の選び方に左右される。再帰の各段階で常に均等に分割される場合が最良で、常に「１要素と残り全部」のような偏った分割となると最も効率が悪くなる。
- これを防ぐための工夫としては、なるべく配列の中央値をピボットとして選ぶ、分割前に配列をランダムに並び替える、などがあるが、いずれも最悪のケースを完全排除できるわけではない。
- 根本的な対処として、再帰が一定数を越えたらヒープソートのようなnlogn時間が保証されるアルゴリズムに切り替える、などがある。
- また、分割後の要素数が一定数以下になったら挿入ソートのような「少数の要素に対してより効率的なソートアルゴリズム」に切り替えることでもより効率化が見込める。
クイックソートの手順
- 適当な値（ピボット）を境界値として選択する
- ピボット未満の要素を配列の先頭に集めることで、ピボット未満 / ピボット以上のグループに分割する
- 分割されたグループに対して、①②を繰り返す
クイックソートの実装
当然ながら、こうしたソートアルゴリズムに対してはライブラリが用意されており、実用の際には都度一から実装する必要はありません。
これにはnumpyのsort関数が使えます。
https://numpy.org/doc/stable/reference/generated/numpy.sort.html
コード
import random
a = []
for i in range(10):
x = random.randint(1,100)
a.append(x)
np.sort(a, kind='quicksort')#実行結果
array([ 7, 15, 29, 47, 58, 76, 85, 89, 90, 94])ちなみに、実行時間を計測してみると、配列要素数5000程度まではまったく時間がかからず、5000を超えると指数的に時間が増えていっていくことが分かります。（とはいえ、1000万要素数でも2秒ちょい・・十分早い気がする・・）
が、これでは理解も深まらないので、手動でも実装してみたいと思います。実装は、参考文献に記載のサイトのコードを利用させていただきました。
コードは以下の通りになります。
def quick_sort(arr):
left = []
right = []
if len(arr) <= 1:
return 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
# 先ほどの配列を代入
quick_sort(a)#実行結果
[7, 15, 29, 47, 58, 76, 85, 89, 90, 94]参考文献
今回大変参考にさせていただいた記事をここにまとめておきます。
https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88
https://qiita.com/suecharo/items/30f5d817da4c948c3be6
http://www.math.u-ryukyu.ac.jp/~suga/C/2004/13/node4.html
コメントを残す