クイックソート（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、現在で一番高速な整列アルゴリズムであるクイックソート（Quick Sort）について学んでいきます。

クイックソートとは
クイックソートの計算量
Pythonでクイックソートを実装してみる
動作確認
参考書籍

クイックソートとは

クイックソート（Quick Sort）とは、1962年にC.A.R.Hoareによって発見されたアルゴリズムで、現在最も高速な整列アルゴリズムとして知られています。

クイックソートでは、ある基準となる値（枢軸：Pivot）を決めて、その値より小さいものは左、大きいものは右に振り分けていきます。

以下のfig1はソート前の状態で、ここでは5を枢軸としてソートをしてみます。

以下のfig2はソートを行った後の状態です。

そして、上記リストのインデックス0～2、4～7までを同じようにソートしてくと、最終的にリスト全体の整列が完了します。

また、このように部分的に分割して問題を解決するアプローチを分割統治（Divide and Rule or Divide and Conquer）と呼び、クイックソートでは再帰呼び出し（Recursive Call）を行うことで実行しています。

なお、クイックソートは安定な整列アルゴリズム（データの位置関係が保存される）ではありません。

クイックソートの計算量

クイックソートでは $O(n \log n)$ の計算量となりますが、前述した枢軸の決定方法次第で、最悪の場合は $O(n^2)$ となってしまいます。

また、クイックソートでは再帰呼び出しを行うため、再帰呼び出しを行うたびに呼び出し元への戻りアドレスや、呼び出し先で使うローカル変数などがメモリ上のスタック領域に積まれていくため、最悪の場合ではスタック領域のメモリを大幅に消費します。

上記のfig1のように枢軸を右端にした場合、データ数が多いと分割が続き効率が大幅に下がります。

Pythonでクイックソートを実装してみる

それでは、Pythonでクイックソートを実装してみます。

# quick_sort.py
import time
import pickle

def quick_sort_sub(lst, left, right):
    l = left
    r = right
    pivot = lst[int((left+right)/2)]

    while l <= r:
        while lst[l] < pivot:
            l += 1
        while lst[r] > pivot:
            r -= 1
        if l <= r:
            tmp = lst[l]
            lst[l] = lst[r]
            lst[r] = tmp
            l += 1
            r -= 1
    if r > left:
        quick_sort_sub(lst, left, r)
    if l < right:
        quick_sort_sub(lst, l, right)

def quick_sort(lst):
    quick_sort_sub(lst, 0, len(lst)-1)

with open('sample_data.pkl', 'rb') as f:
    lst = pickle.load(f)

start = time.time()
quick_sort(lst)
print("elapsed {} sec".format(time.time() - start))