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

1.ソートの挿入(章2.1)

def insertion_sort(A):
    for i in range(1, len(A)):
        key = A[i]
        while i > 0 and key < A[i-1]: //      ，    key       key        
            A[i] = A[i-1]
            i -= 1
        A[i] = key
    return A


P = [3, 2, 1, 4, 6, 5, 9]
print(insertion_sort(P))

2.集計ソート(章2.3.1)

def merge(A, p, r, q):

    L = []
    R = []
    for i in range(p, r+1):
        L.append(A[i])
    L.append(float('inf'))
    print(L)
    for j in range(r+1, q+1):
        R.append(A[j])
    R.append(float('inf'))
    print(R)
    i = 0
    j = 0
    for k in range(p, q+1):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return A


def merge_sort(A, p, q):
    if p < q:
        r = (p + q) // 2  #integer division
        merge_sort(A, p, r)
        merge_sort(A, r+1, q)
        print(merge(A, p, r, q))

P = [5, 2, 3]
merge_sort(P, 0, 2)

3.最大子配列問題暴力解法(章節4.1)

def violent_solution(A):
    profit = 0
    buy = ''
    sale = ''
    for key1 in A:
        for key2 in A:
            if int(key1) < int(key2) and A[key1] < A[key2] and profit < (A[key2] - A[key1]):
                profit = A[key2] - A[key1]
                buy = key1
                sale = key2
    return buy, sale, profit


P = {'0': 100, '1': 113, '2': 110, '3': 85, '4': 105, '5': 102,
     '6': 86, '7': 63, '8': 81, '9': 101, '10': 94, '11': 106,
    '12': 101, '13': 79, '14': 94, '15': 90, '16': 97}

print(violent_solution(P))

4.最大サブ配列問題の分治戦略解法(midは左側に計算)(章4.1)

import math


def find_max_crossing_subarray(A, low, mid, high):
    left_sum = float('-inf')
    s = 0
    max_left = 0
    for i in range(low, mid+1)[::-1]:
        s = s + A[i]
        if left_sum < s:
            left_sum = s
            max_left = i
    right_sum = float('-inf')
    s = 0
    max_right = 0
    for j in range(mid+1, high+1):
        s = s + A[j]
        if right_sum < s:
            right_sum = s
            max_right = j
    return max_left, max_right, left_sum + right_sum


def find_maximum_subarray(A, low, high):
    if low == high:
        return low, high, A[low]
    else:
        mid = math.floor((low + high) / 2)
        left_low, left_high, left_sum = find_maximum_subarray(A, low, mid)
        right_low, right_high, right_sum = find_maximum_subarray(A, mid+1, high)
        cross_low, cross_high, cross_sum = find_max_crossing_subarray(A, low, mid, high)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_low, left_high, left_sum
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return right_low, right_high, right_sum
        else:
            return cross_low, cross_high, cross_sum


P = [100, 113,  110,  85,  105, 102, 86,  63,  81,  101,  94,  106, 101,  79,  94,  90,  97]
P_C = []
for i in range(1, P.__len__()):
    P_C.append(P[i] - P[i-1])

print(find_maximum_subarray(P_C, 0, 15))

5.最も大きなサブ配列問題の分治戦略解法(midは右側に計算)(章4.1)
(この場合区間を変更する必要があるほか、midの取値を上向きにする必要がある)

import math


def find_max_crossing_subarray(A, low, mid, high):
    left_sum = float('-inf')
    s = 0
    max_left = 0
    for i in range(low, mid)[::-1]:
        s = s + A[i]
        if left_sum < s:
            left_sum = s
            max_left = i
    right_sum = float('-inf')
    s = 0
    max_right = 0
    for j in range(mid, high+1):
        s = s + A[j]
        if right_sum < s:
            right_sum = s
            max_right = j
    return max_left, max_right, left_sum + right_sum


def find_maximum_subarray(A, low, high):
    if low == high:
        return low, high, A[low]
    else:
        mid = math.ceil((low + high) / 2)  //        
        left_low, left_high, left_sum = find_maximum_subarray(A, low, mid-1)
        right_low, right_high, right_sum = find_maximum_subarray(A, mid, high)
        cross_low, cross_high, cross_sum = find_max_crossing_subarray(A, low, mid, high)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return left_low, left_high, left_sum
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return right_low, right_high, right_sum
        else:
            return cross_low, cross_high, cross_sum


P = [100, 113,  110,  85,  105, 102, 86,  63,  81,  101,  94,  106, 101,  79,  94,  90,  97]
P_C = []
for i in range(1, P.__len__()):
    P_C.append(P[i] - P[i-1])

print(find_maximum_subarray(P_C, 0, 15))

6.ランダム配列の生成(章5.3)

import random

def randomize_in_place(A):
    for i in range(len(A)):
        r = random.randint(i, len(A)-1)
        A[i], A[r] = A[r], A[i]
    return A


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