アルゴリズム導論第7章高速ソート(python)
2918 ワード
最も多く使用されるソート
平均性能:O(nlogn){ランダム化nlogn}
元のアドレスのソート
安定性あんていせい:不安定
思想:分治(左右を切り分ける)
学習方法:自分で紙の上で一回歩きます
ランダムクイックソート
平均性能:O(nlogn){ランダム化nlogn}
元のアドレスのソート
安定性あんていせい:不安定
思想:分治(左右を切り分ける)
学習方法:自分で紙の上で一回歩きます
def PARTITION(A,p,r):
x = A[r] # { ， }
i = p - 1
for j in range(p,r):
if A[j] <= x:
i += 1
A[i],A[j] = A[j],A[i]
A[i+1],A[r] = A[r],A[i+1]
return i + 1
def QUICKSORT(A,p,r):
if p < r: #
q = PARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)
if __name__ == "__main__":
A = [2,8,7,1,3,5,6,4]
QUICKSORT(A,0,len(A)-1)
print(A)
'''
=============== RESTART: F:/python/algorithms/7_1_quicksort.py ===============
[1, 2, 3, 4, 5, 6, 7, 8]
win7+python3.5.1
'''ランダムクイックソート
import random
def PARTITION(A,p,r):
x = A[r] # { ， }
i = p - 1
for j in range(p,r):
if A[j] <= x:
i += 1
A[i],A[j] = A[j],A[i]
A[i+1],A[r] = A[r],A[i+1]
return i + 1
def RANDOMIZED_PARTITION(A,p,r):
i = random.randint(p,r) #
A[i],A[r] = A[r],A[i]
return PARTITION(A,p,r)
def RANDOMIZED_QUICKSORT(A,p,r):
if p < r: #
q = RANDOMIZED_PARTITION(A,p,r)
RANDOMIZED_QUICKSORT(A,p,q-1)
RANDOMIZED_QUICKSORT(A,q+1,r)
if __name__ == "__main__":
A = [2,8,7,1,3,5,6,4]
RANDOMIZED_QUICKSORT(A,0,len(A)-1)
print(A)
'''
=============== RESTART: F:/python/algorithms/7_1_quicksort.py ===============
[1, 2, 3, 4, 5, 6, 7, 8]
win7+python3.5.1
'''