アルゴリズム導論(Pythonバージョン)(第9章)

1.ソートの選択

import random

def PARTION(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_PARTION(A, p, r):
    i = random.randint(p, r)
    A[i], A[r] = A[r], A[i]
    return PARTION(A, p, r)


def RANDOMIZED_SELECT(A, p, r, i):  #    A[p...r]  i    
    if p == r:
        return A[p]
    q = RANDOMIZED_PARTION(A, p, r)
    k = q - p + 1
    if k == i:
        return A[q]
    elif i < k:
        return RANDOMIZED_SELECT(A, p, q-1, i)
    else:
        return RANDOMIZED_SELECT(A, q+1, r, i - k)


a = [324, 99, 3, 392, 543, 573]
print(RANDOMIZED_SELECT(a, 0, 5, 3))

2.最悪の場合は線形時間の選択アルゴリズム

def INSERTION_SORT(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i+1] = A[i]
            i -= 1
        A[i+1] = key
    return A


def PARTION(A, p, r, k):
    A[r], A[k] = A[k], A[r]
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1


def SELECT(A, p, r, i):

    if p == r:
        return A[p]

    B = []
    for j in range(p, r+1, 5):
        B.append(A[j:j+5])

    xs = []
    for b in B:
        b = INSERTION_SORT(b)
        xs.append(b[int((len(b)-1)/2)])

    xs_sorted = INSERTION_SORT(xs)
    x = xs_sorted[int((len(xs_sorted) - 1) / 2)]

    x_i = 0
    for a in range(p, r + 1):
        if x == A[a]:
            x_i = a

    k = PARTION(A, p, r, x_i)

    if i == k:
        return x
    elif i < k:
        return SELECT(A, p, k-1, i)
    else:
        return SELECT(A, k+1, r, i-k)


A = [1,2,3,4,5,6,7,8,9]
print(SELECT(A, 0, 8, 9))