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