アルゴリズム導論第7章高速ソート(python)

最も多く使用されるソート
平均性能: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

'''