クイックソートについて自分用にメモを書いてみました。
クイックソートとは
- 分割統治法に基づく高速なソートアルゴリズムで、大きなデータサイズに対応できる。
- 計算量はO(nlogn)
- logn個の階層があり、各層ごとの計算量はO(n)であるため。
- ソートすると同じ値の順序が変わってしまう不安定なソート
- 一時的にデータを保存するメモリは必要ない
コード
quick_sort.py
def partition(A, p, r):
x = A[r-1]
i = p-1
for j in range(p, r-1):
if A[j] <= x:
i += 1
A[i], A[j] = A[j], A[i]
A[i+1], A[r-1] = A[r-1], A[i+1]
return i+1
n = int(input())
A = list(map(int, input().split()))
def quick_sort(A, p, r):
if p < r:
q = partition(A, p, r)
quick_sort(A, p, q)
quick_sort(A, q+1, r)
return A
print(quick_sort([3, 1, 10, 2.5, 11, 3, 21,4, -1], 0, 9))
# [-1, 1, 2.5, 3, 3, 4, 10, 11, 21]
上記のアルゴリズムは基準の選び方が一定（最後尾の値）なので、データの並びによっては効率が悪くなる
計算量がO(n^2)になるかも
再帰が深くなりすぎてエラーになるかも
そのため、基準の選び方をランダムにする、中央値を選ぶなど工夫する必要がある。