[Python] クイックソートの実装方法とアルゴリズム

Pythonとクイックソート

Pythonでクイックソートを実装してみます。Python3.6を使います。

クイックソートは数あるソートアルゴリズムの中でも、実用上最速とされる誉れ高いアルゴリズムです。ただし条件次第で低速になってしまうので注意が必要です。

クイックソートは分割統治法と呼ばれる考え方を使ってソートを行います。まずソート対象のデータ(リスト)について、ピボット(基準値)を選び、その基準値より小さい値を前の方、大きい値を後ろの方に移動します。この手順を前半と後半それぞれの部分について再帰的に呼び出すことで、大きな範囲から徐々に小さな範囲をソートしていきます。最終は2つの要素からなる範囲について、正しい順序で並ぶのでソートが正しく行われるという次第です。

平均計算量は O(n log n) となります。再帰的に要素を分割していく処理を行うので log n が出現しているようです。最悪のケース(ピボットの選び方が原因)では、計算量が O(n²) となってしまいます。

例えばすでにソート済のデータについてクイックソートを適用する場合に、ピボットとして先頭要素を選ぶことにした際などが最悪の計算量となります。分割によってデータ1件ずつが処理されるので、結局全データを2重でループする場合と同じことになってしまいます。このような状況に陥らないように、ピボットの選び方を工夫してやる必要があります。以下のサンプルでは、ソート対象データの先頭/中央/末尾の3値から中央値となる値をピボットに採用しています。

以下サンプルソースです。

def _quick_sort(array, left, right):
    if left >= right: return

    # ピボットを決定
    pivot = median(array[left], array[(left + (right - left) // 2)], array[right])
    l = left
    r = right

    # ピボットを中心に分ける
    while True:
        # ピボットより小さい値を左、大きい値を右に移動する
        while array[l] < pivot:
            l += 1
        while pivot < array[r]:
            r -= 1
        if (r <= l): break

        # 見つかった要素を交換
        tmp = array[l]
        array[l] = array[r]
        array[r] = tmp
        l += 1
        r -= 1

    # 左右に分けた部分を再帰的にクイックソート
    _quick_sort(array, left, l - 1)
    _quick_sort(array, r + 1, right)

def quick_sort(array):
    _quick_sort(array, 0, len(array)-1)

def median(x, y, z):
    if x < y:
        return (y if y < z else z) if x < z else x
    else:
        return (x if x < z else z) if y < z else y

# デバッグ
if __name__ == "__main__":
    array = [1,2,3,4,5,3,2,1,4,3,4,5,0]
    print("before", array)
    quick_sort(array)
    print("after ", array)

参考URL

• クイックソート – Algoful
• クイックソート – Wikipedia