クイックソートはリストにおいてピボットと呼ぶ要素を軸に分割を繰り返して整列を行うアルゴリズムです。

「分割を繰り返して整列を行う」ような手法を分割統治法 divide-and-conquer と呼びます。

アルゴリズム分析

1. 要素数が1つかそれ以下なら整列済みとみなしてソート処理を行わない
2. ピボットとなる要素をピックアップする
3. ピボットを中心とした2つの部分に分割する - ピボットの値より大きい値を持つ要素と小さい値を持つ要素
4. 分割された部分(サブリスト)に再帰的にこのアルゴリズムを適用する

分割統治法は手順 4. にあるように再帰処理で実現されます。

分割統治法 divide-and-conquer

分割統治法とは大きな問題を小さな問題に分割することによって全体を解決しようとする方法です。

クイックソートではピボットと呼ぶ軸となる要素の値より大きい要素群、小さい要素群という具合にソートの対象となる部分を小さくしてゆきながら全体のソートを完了させます。

図解

特徴

ソートアルゴリズムのなかで最も高速なアルゴリズムです。しかし、アルゴリズムが理解しやすいわりにはC言語なんかでのプログラミングは難しいです。

サンプルコード

Python

リストを昇順に整列させる実装例です。

ピボットをリストの先頭要素として、値の小さな要素は left リストに、値の大きな要素は right リストに格納して最後にピボットを中心としてリストを結合しています。

def quicksort(seq):
    if len(seq) < 1:
        return seq
    pivot = seq[0]
    left = []
    right = []
    for x in range(1, len(seq)):
        if seq[x] <= pivot:
            left.append(seq[x])
        else:
            right.append(seq[x])
    left = quicksort(left)
    right = quicksort(right)
    foo = [pivot]
    return left + foo + right

C言語

C言語で配列を昇順に整列させる実装例です。

void q_sort(int numbers[], int left, int right)
{
    int pivot, l_hold, r_hold;

    l_hold = left;
    r_hold = right;
    pivot = numbers[left];
    while (left < right)
    {
        while ((numbers[right] >= pivot) && (left < right))
            right--;
        if (left != right)
        {
            numbers[left] = numbers[right];
            left++;
        }
        while ((numbers[left] <= pivot) && (left < right))
            left++;
        if (left != right)
        {
            numbers[right] = numbers[left];
            right--;
        }
    }
    numbers[left] = pivot;
    pivot = left;
    left = l_hold;
    right = r_hold;
    if (left < pivot)
        q_sort(numbers, left, pivot-1);
    if (right > pivot)
        q_sort(numbers, pivot+1, right);
}

解説

リストの左端の要素がピボットになります。left はピボットより小さい値を持つ要素を指し、right がピボットより大きな値を持つ要素を指します。left, right を交換することで条件に一致する要素を振り分けた後、ピボットと left の要素を交換します。

そして、ピボットから左側の要素とピボットから右側の要素を対象に再帰処理でソートを完了させます。

クイックソートのデモンストレーション プログラム: quick_sort.c

• シェルソート
• マージソート

---