[ソート] クイックソート

クイックソート

クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

良く使われるソートのアルゴリズムです。

分割統治法によるアルゴリズムで、「配列の中から ‘pivot’ と呼ばれる適当な数を選び、 ‘pivot’ を基準にそれより小さい数を ‘pivot’ より前に、大きい数を ‘pivot’ より後に並べる」という処理を行うことで、当然ながら ‘pivot’ より前にはより小さい数が ‘pivot’ より後には大きい数が並びます。

次に ‘pivot’ を基準に配列を2分割し、同様の処理を行います。

最終的に、配列のサイズが0か1になるまで再帰的に処理することで、ソートされます。

下記は、配列の最後を ‘pivot’ をとする場合のクイックソートの例です。

配列の最後を ‘pivot’ をとする場合のクイックソート

バブルソートなど\( O ( N^2) \)の計算量のソートアルゴリズムに対し、クイックソートの平均計算量は\( O ( \log N ) \) で効率的なソートアルゴリズムになります。最悪計算量は \( O ( \log N^2 ) \) になりますが、乱択アルゴリズムを用いることで、最悪の状態をほぼ避けることができます。

内部ソートですが、安定ソートではありません。

クイックソートの計算量の証明

Average-case analysis

下記動画で 50:00ごろからクイックソート、 1:08:00ごろから乱択アルゴリズムを用いるクイックソートの計算量について解説しています。

6. Randomization: Matrix Multiply, Quicksort

クイックソートとマージソートの比較

Quick Sort vs Merge Sort

	クイックソート	マージソート
配列の分割	2等分とは限らない	2等分される
最悪計算量	\( O ( N^2) \)	\( O ( N \log N ) \)
内部ソート	内部ソートである	内部ソートではない
安定ソート	安定ソートではない	安定ソートである
型による相性	配列	連結リスト
参照局所性	良い	悪い

Python での実装

Python で実装します。

‘pivot’ はランダムに選ぶことにします。

import random

def quick_sort(array, low_index, high_index):
    if low_index < high_index:
        # pivot より小さい要素を左側に、pivot より大きい要素を右側に持って行って分割。
        pivot_index = partition(array, low_index, high_index)
        # 分割した左側を再帰的にソート
        quick_sort(array, low_index, pivot_index -1)
        # 分割した右側を再帰的にソート
        quick_sort(array, pivot_index+1, high_index)
    
    return array

def partition(array, low_index, high_index):
    # pivot をランダムに選ぶ
    pivot_index = low_index + random.randrange(high_index - low_index + 1)
    # pivot は配列の一番右側に配置し、array[high_index] が pivot になる。
    array[high_index], array[pivot_index] = array[pivot_index], array[high_index]
    # pivot と他の要素を比較
    for i in range(low_index, high_index):
        # ある要素がpivotより小さい場合
        if array[i] < array[high_index]:
            # その要素は左端と交換
            array[i], array[low_index] = array[low_index], array[i]
            # 左端は pivot より小さい要素として固定され、ポインタを右に一つ進める。
            low_index += 1

    # pivot を pivot より小さい要素の右側にすることで、array[low_index] が pivot になる。
    array[low_index], array[high_index] = array[high_index], array[low_index]
    # 再帰のため pivot のインデックスを返す。
    return low_index


if __name__ == '__main__':

    random.seed(1)
    array = [random.randrange(100) for i in range(10)]
    print('未ソート', array)
    # 未ソート [17, 72, 97, 8, 32, 15, 63, 97, 57, 60]
    print('ソート済み', quick_sort(array, 0, len(array)-1)) 
    # ソート済み [8, 15, 17, 32, 57, 60, 63, 72, 97, 97]