アルゴリズムイントロダクション第3版の疑似コードから4種類のソートをPythonで実装する

はじめに

「アルゴリズムイントロダクション第 3 版 (第 1 巻)」では，いくつかのソートが紹介されている．その疑似コードをもとに，

• 挿入ソート
• マージソート
• ヒープソート
• クイックソート

を Python で実装する．
疑似コードと同じ手順で，変数の名前も真似していく．
以下に書いたソートの関数に渡す引数 A は全て，でたらめな順番で要素が並んでいるリスト．

挿入ソート

挿入ソートは，次のように書ける:

insertion_sort.py

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

マージソート

マージソートは，2 つの部品で作る．

• MERGE: 整列された 2 つの配列を合体して 1 つの整列された配列にする
• MERGE-SORT: 再帰呼び出しで細分化した配列を順に MERGE していく

merge_sort.py

def merge(A, p, q, r):
    n_1 = q - p + 1
    n_2 = r - q
    L = []
    R = []
    for i in range(n_1):
        L.append(A[p + i])
    for j in range(n_2):
        R.append(A[q + j + 1])
    L.append(SENTINEL)
    R.append(SENTINEL)
    i, j = 0, 0
    for k in range(p, r + 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=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = (p + r) // 2
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)
    return A

ヒープソート

前準備: ヒープを表現する

ヒープソートでは，ヒープという構造を使う．
まず前準備として，ヒープを Python で表現するために，Heap クラスを作る．
これは，Python のビルトインオブジェクトである list に，heap_size という属性を追加したもの．

heap_sort.py

class Heap(list):
    def __init__(self, *args):
        super().__init__(*args)
        self.heap_size = len(self)

この Heap は，リストとしての機能を保っている．試しに次のように書く:

heap = Heap([1, 2, 3, 2, 3, 4])
print("heap:", heap)
print("heap.heap_size:", heap.heap_size)
print("len(heap):", len(heap))

実行結果は次のようになる:

heap: [1, 2, 3, 2, 3, 4]
heap.heap_size: 6
len(heap): 6

いざ，ヒープソート

ヒープソートは，5 つの部品でできる．

• LEFT: ヒープを 2 分木で表したときに，自分を親として左の子にあたる要素を返す
• RIGHT: 自分を親として右の子を返す RIGHT 手続き
• MAX-HEAPIFY: 根より下がヒープになってるとして，根を適切な位置に移動して全体をヒープにする
• BUILD-MAX-HEAP: 完全にでたらめな配列を MAX-HEAPIFY 何回も使って全体をヒープにする
• HEAP-SORT: 根を取り出して残りをヒープとして修復する操作で配列全体をソートする．

これらを，前準備で作った Heap クラスを用いると，以下のようになる:

heap_sort.py

def left(i):
    return 2 * (i + 1) - 1

def right(i):
    return 2 * (i + 1)

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    if l <= A.heap_size - 1 and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= A.heap_size - 1 and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def build_max_heap(list_A):
    A = Heap(list_A)
    A.heap_size = len(A)
    for i in reversed(range((len(A) - 1) // 2 + 1)):
        max_heapify(A, i)
    return A

def heap_sort(list_A):
    A = build_max_heap(list_A)  # ここで A は Heap クラスのインスタンスになる
    for i in reversed(range(1, len(A))):
        A[0], A[i] = A[i], A[0]
        A.heap_size = A.heap_size - 1
        max_heapify(A, 0)
    return A

クイックソート

クイックソートは，2 つの部品でできる．

• PARTITION: $A[p..r]$ をピボット以下の要素だけでできた $A[p..q-1]$ と，ピボットより大きい要素だけでできた $A[q+1..r]$ の 2 つに分ける
• QUICK-SORT: PARTITION を再帰的に呼び出して $A[p..r]$ 全体をソートする

ピボットは $A[r]$ つまり一番右の要素としている．

quick_sort.py

def partition(A, p, 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 quick_sort(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)
    return A

おまけ: 非増加順 (降順) にソートする

ここまでで作った 4 種類のソートは全て，一番左が小さいもので，右にいくにつれて大きくなっていく順番にするもの．おまけとして，4 種類の逆順のソートを作っておく．
関数の名前は，(ソートの名前)_nonincreasing のようになっている．

もとのソート関数から書き換えた部分にコメントアウトで簡単な説明を加えている．

insertion_sort_nonincreasing.py

def insertion_sort_nonincreasing(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] < key:  # and 以降の不等式の向き変更
            A[i + 1] = A[i]
            i -= 1
        A[i + 1] = key
    return A

merge_sort_nonincreasing.py

SENTINEL_SMALL = - float('inf')  # 番兵をマイナス無限大にする

def merge_nonincreasing(A, p, q, r):
    n_1 = q - p + 1
    n_2 = r - q
    L = []
    R = []
    for i in range(n_1):
        L.append(A[p + i])
    for j in range(n_2):
        R.append(A[q + j + 1])
    L.append(SENTINEL_SMALL)  # マイナス無限大の番兵を用いる
    R.append(SENTINEL_SMALL)  # 同上
    i, j = 0, 0
    for k in range(p, r + 1):
        if L[i] >= R[j]:  # 不等式の向き変更
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return A

def mergeSort_nonincreasing(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = (p + r) // 2
        mergeSort_nonincreasing(A, p, q)      # 自分の名前変更
        mergeSort_nonincreasing(A, q + 1, r)  # 同上
        merge_nonincreasing(A, p, q, r)       # 非増加順にマージする
    return A

heqp_sort_nonincreasing.py

def min_heapify(A, i):  # 名前を min_heapify にする
    l = left(i)
    r = right(i)
    if l <= A.heap_size - 1 and A[l] < A[i]:  # and 以降の不等式の向き変更
        smallest = l  # largest ではなく smallest に変更
    else:
        smallest = i
    if r <= A.heap_size - 1 and A[r] < A[smallest]:  # and 以降の不等式の向き変更
        smallest = r
    if smallest != i:
        A[i], A[smallest] = A[smallest], A[i]
        min_heapify(A, smallest)  # max_heapify ではなく min_heapify


def build_min_heap(list_A):  # 名前を build_min_heap にする
    A = Heap(list_A)
    A.heap_size = len(A)
    for i in reversed(range((len(A) - 1) // 2 + 1)):
        min_heapify(A, i)  # max_heapify ではなく min_heapify
    return A


def heapSort_nonincreasing(list_A):
    A = build_min_heap(list_A)  # build_max_heap ではなく build_min_heap
    for i in reversed(range(1, len(A))):
        A[0], A[i] = A[i], A[0]
        A.heap_size = A.heap_size - 1
        min_heapify(A, 0)  # max_heapify ではなく min_heapify
    return A

quick_sort_nonincreasing.py

def partition_nonincreasing(A, p, 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 quickSort_nonincreasing(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = partition_nonincreasing(A, p, r)  # nonincreasing 版を呼ぶ
        quickSort_nonincreasing(A, p, q - 1)  # 同上
        quickSort_nonincreasing(A, q + 1, r)  # 同上
    return A