アルゴリズム勉強 #4 クイックソートをpythonで実装する
2021.10.26
今回はクイックソートです！
- 配列から基準点を決める
- 基準値より小さい（left）と大きい（right）に分ける
- 計算量は平均O(nlogn), 最悪O(n**2)
- 最悪は分割がn-1個と0個の分割が最後まで続く場合
- Tn（サイズnの配列を整列させるのに必要な回数
- Tn = n - 1 + Tn-1 = (n-1) + (n-2) + ... = n(n-1)/2
- 最良は分割が2分割でキレイに進む
- 分割はlogn(=k)回
- 分割が1回進んだとき2**(k-1)の配列が2つ
- このときの比較回数が2(2**(k-1) - 1) = n-2 ~ n
- O(nlogn)
試したコード
## merge sort
import random
def quick_sort(array):
left = []
right = []
if len(array) <= 1:
return array
ref = random.choice(array)
count = 0
for element in array:
if element < ref:
left.append(element)
elif element > ref:
right.append(element)
else:
count += 1
left = quick_sort(left)
right = quick_sort(right)
return left + [ref] * count + right
array = [i+1 for i in range(30)]
random.shuffle(array)
quick_sort(array)
