Pythonでクイックソートを書いてみたメモ
クイックソートについて自分用にメモを書いてみました。
クイックソートとは
- 分割統治法に基づく高速なソートアルゴリズムで、大きなデータサイズに対応できる。
- 計算量は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]
- 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)になるかも
再帰が深くなりすぎてエラーになるかも
そのため、基準の選び方をランダムにする、中央値を選ぶなど工夫する必要がある。
参考
Author And Source
この問題について(Pythonでクイックソートを書いてみたメモ), 我々は、より多くの情報をここで見つけました https://qiita.com/rA9-S/items/240ecd306082f79c9133著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .