algorithm - ヒープソート

ワーストケースでも O (n log (n)) なパフォーマンスが出せる。
* ベストもアベレージも O (n log (n))
ただし、平均速度はクイックソートの方が上。

def comp(a, b):
    if a > b:
        return 1
    elif a < b:
        return -1
    else:
        return 0

# 親と子を比較し、子の方が大きければ交換
# 交換があれば更なる交換がないか再帰的に調べる
def heapify(arr, comp_func, idx, max_idx):
    left = 2 * idx + 1
    right = 2 * idx + 2
    largest = 0
    if left < max_idx and comp_func(arr[left], arr[idx]) > 0:
        largest = left
    else:
        largest = idx
    if right < max_idx and comp_func(arr[right], arr[largest]) > 0:
        largest = right
    if largest != idx:
        tmp = arr[idx]
        arr[idx] = arr[largest]
        arr[largest] = tmp
        heapify(arr, comp_func, largest, max_idx)

# 子は必ず親より小さい、という性質を持つ 2 分木を作成する
# 大きい数字が勝ち上がっていく、トーナメントのようなイメージ
def buildHeap(arr, comp_func, n):
    for i in range(n / 2 - 1, -1, -1):
        heapify(arr, comp_func, i, n)
        
def heapSort(arr, n, comp_func):
    # 初回のみ下から木を作る
    buildHeap(arr, comp_func, n)
    for i in range(n - 1, 0, -1):
        # 最大値が配列先頭にあるので、終端と交換
        tmp = arr[0]
        arr[0] = arr[i]
        arr[i] = tmp
        # 一度木が作成済みなので先頭から交換の有無を調べる
        # 上位に交換がなければ、下位に影響はない
        heapify (arr, comp_func, 0, i)
        
a = range(0, 500)
random.shuffle(a)
print a
heapSort(a, len(a), comp)
print a

algorithm - クイックソート

Median Sort と基本的な方法は同じ。
Median を選ばず適当な位置をピボットに配列を分割する。
ワーストケースパフォーマンスを避けるために単純なランダムでないバリエーションもある。
(Median-of-three 等)
配列が小さい時は挿入ソートの方が速くなるので、 サイズが一定以下になったら挿入ソートを使う。

def selectPivotIndex(left, right):
    return random.randint(left, right + 1)

# 配列を、pivotIndex の値で分割する。
# pivotIndex の値より小さい値は前、
# pivotIndex の値より大きい値は後ろに移動
def partition(arr, comp_func, left, right, pivotIndex):
    # pivot の値を最後尾に移動
    pivot = arr[pivotIndex]
    tmp = arr[right]
    arr[right] = pivot
    arr[pivotIndex] = tmp
    
    # pivot より小さい値を前に持っていく
    store = left
    for i in range(left, right):
        if comp_func(arr[i], pivot) < 0:
            tmp = arr[i]
            arr[i] = arr[store]
            arr[store] = tmp
            store += 1
    # pivot を配置
    tmp = arr[store]
    arr[store] = pivot
    arr[right] = tmp
    return store

# 挿入ソート
def insertion(arr, comp_func, left, right):
    for i in range(left, right + 1):
        tmp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] >= tmp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = tmp

# 最大深さを記録。特に意味は無い。
max_depth = 0
# 配列サイズがこれ以下なら挿入ソートを使う
MIN_SIZE = 4

def qsort(arr, comp_func, left, right, depth):
    if right <= left:
        return
    pivotIndex = selectPivotIndex(left, right)
    pivotIndex = partition(arr, comp_func, left, right, pivotIndex)
    # サイズが一定以下なら挿入ソート
    if pivotIndex <= MIN_SIZE:
        # グローバル変数にアクセスするには global 宣言が必要
        global max_depth
        max_depth = max(max_depth, depth)
        insertion(arr, comp_func, left, pivotIndex - 1)
    else:
        qsort(arr, comp, left, pivotIndex - 1, depth + 1)
    if right - pivotIndex - 1 <= MIN_SIZE:
        global max_depth
        max_depth = max(max_depth, depth)
        insertion(arr, comp_func, pivotIndex + 1, right)
    else:
        qsort(arr, comp, pivotIndex + 1, right, depth + 1)

a = range(1, 500)
random.shuffle(a)

print a

qsort(a, comp, 0, len(a) - 1, 0)

print max_depth
print a

algorithm - Median Sort

クイックソートの下準備的な知識になるらしい。

def comp(a, b):
    if a > b:
        return 1
    elif a < b:
        return -1
    else:
        return 0

# 配列を、pivotIndex の値で分割する。
# pivotIndex の値より小さい値は前、
# pivotIndex の値より大きい値は後ろに移動
def partition(arr, comp_func, left, right, pivotIndex):
    # pivot の値を最後尾に移動
    pivot = arr[pivotIndex]
    tmp = arr[right]
    arr[right] = pivot
    arr[pivotIndex] = tmp
    
    # pivot より小さい値を前に持っていく
    store = left
    for i in range(left, right):
        if comp_func(arr[i], pivot) <= 0:
            tmp = arr[i]
            arr[i] = arr[store]
            arr[store] = tmp
            store += 1
    # pivot を配置
    tmp = arr[store]
    arr[store] = pivot
    arr[right] = tmp
    return store

# 適当
def selectPivotIndex(left, right):
    return right

# K 番目の値を取得する。
# 返却値はインデックスだが arr が変化した後のインデックスなので
# 元の配列でどこにあったか、といったような情報ではない。
# あくまで値のみ。
# 結果として K 番目の値で配列が分割されている。
def selectKth(arr, comp_func, k, left, right):
    # 適当に pivot を選択
    pivotIndex = selectPivotIndex(left, right)
    # pivot で分割
    pivotIndex = partition(arr, comp_func, left, right, pivotIndex)
    # pivot が  K 番目だったら終了。
    if left + k == pivotIndex:
        return pivotIndex
    # pivot が K よりも大きければ、前方の配列から再度探す。
    elif left + k < pivotIndex:
        return selectKth(arr, comp_func, k, left, pivotIndex - 1)
    # pivot が K よりも小さければ、後方の配列から再度探す。
    else:
        return selectKth(arr, comp_func, (left + k) - pivotIndex - 1, pivotIndex + 1, right)

def medianSort(arr, comp_func, left, right):
    # 配列のサイズが 1 であれば終了
    if right <= left:
        return
    mid = (right - left) + 1 / 2
    # 配列を中央値で再帰的に分割
    selectKth(arr, comp_func, mid, left, right)
    medianSort(arr, comp_func, left, left + mid - 1)
    medianSort(arr, comp_func, left + mid + 1, right)

a = [1,5,2,7,9,32,6,87,9,21,6,43,556,14,69]

medianSort(a, comp, 0, len(a) - 1)

print a

algorithm - 挿入ソート

低速だけど安定で実装しやすい。ほとんど整列済みのデータに対しては高速。
さらに、ソート対象が連結リストであれば、挿入が高速にできるのでバブルソートよりも 大幅に速い。

データを1つずつ、手持ちのデータの中で正しい位置に挿入しながら、
段々とデータ数を増やしていくイメージ。

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        tmp = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > tmp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = tmp