Pythonでクイックソートを実装する方法！仕組みからコード例まで徹底解説

Pythonのクイックソート（QuickSort）は、ピボットと呼ばれる基準となる要素を選び、配列の要素を2つの新しい配列に分割するソートアルゴリズムです。ピボットより大きい数値は一方の配列へ、小さい数値はもう一方の配列へ振り分けられます。その後、それぞれの配列が再帰的にソートされ、最終的にすべての配列が1つに統合されます。

Pythonでクイックソートをコーディングする方法

プログラミングには、リストを並べ替えるためのさまざまなソートアルゴリズムがあります。挿入ソートやバブルソートなどが代表的ですが、その中でもクイックソートは最もよく使われるアルゴリズムの一つです。

この記事では、クイックソートとは何か、どのように動作するのかを解説し、実際にPythonでクイックソートを実装する例を通して学んでいきます。

Pythonのクイックソートとは？

クイックソートは、配列を複数の部分配列（サブ配列）に分割していくアルゴリズムです。各サブ配列に対して再帰的に処理を呼び出すことで、リスト内のすべての要素をソートします。サブ配列の中身は「ピボット」と呼ばれる基準要素によって決まり、ピボット自体は新しいサブ配列に移動しません。

クイックソートは「分割統治法（divide-and-conquer）」に基づいています。つまり、リスト全体をソートするという大きなタスクを、いくつかの小さなサブタスクに分解し、最後にそれらの結果をまとめてソート済みのリストを返します。

クイックソートにおけるサブタスクとは、各サブリストにピボットを設定し、ピボットとの大小関係に基づいて要素を並べることです。

クイックソートはどんなときに使うべき？

時間計算量が重要な場面では、クイックソートが有効です。他のアルゴリズムと比べてメモリ使用量が少ないため、効率面で優れています。

ただし、クイックソートを使いこなすにはPythonの再帰処理への理解が不可欠です。クイックソートのアルゴリズムは再帰関数に依存しているためです。

また、小規模な配列ではマージソートよりも高速に動作しますが、大規模なデータセットでは挿入ソートやマージソートの方が速くなる場合もあります。

クイックソートの仕組み

クイックソートでは、まずピボットとして使う要素を1つ選びます。これはリスト内のどの要素でも構いません。このチュートリアルでは、リストの最後の要素（3）をピボットとして採用します。

8

4

5

2

1

3

次に、リスト内の各要素をループで走査しながら、ピボットの値と比較します。要素がピボットより大きければピボットの後ろへ、そうでなければピボットの前へ移動させます。

2

1

3

8

5

4

これにより、値3はリスト内で適切な位置に移動しました。3より小さい要素はすべて左側に、3より大きい要素はすべて右側に配置されています。

ここで、元の配列は「ピボットより大きい要素群」と「ピボットより小さい要素群」の2つに分割されます。

分割が完了したら、それぞれの半分に対して新しいピボットを設定し、同じアルゴリズムを独立に適用していきます。まず、各リストの最後の値をピボットとします。

ピボット1			ピボット2
2	1		8	5	4

続いて、ピボットより大きい値を右側へ、小さい値を左側へ移動させます。

ピボット1			ピボット2
1	2		4	8	5

このプロセスを繰り返すことで、リスト全体が整列されていきます。

1回目	1	2		4	8	5
2回目		1			5	8
3回目						8

最終的な配列は次のようになります。

1

2

3

4

5

8

Pythonクイックソートの実装例

クイックソートを実装するには、「partition（分割）関数」と「quick_sort関数」の2つの関数が必要です。

まずはpartition関数から作成しましょう。この関数は、ピボット要素の値に基づいて配列を分割（準備）します。

partition関数の役割は以下の通りです。

1. ピボット要素を選択する
2. ピボットより大きい要素をすべてピボットの右側へ移動する
3. ピボットより小さい要素をすべてピボットの左側へ移動する

クイックソートのPythonプログラム

それでは、このアルゴリズムを実装するプログラムを書いてみましょう。

def prepare(numbers, low, high):
    pivot = numbers[high]
    item = low - 1

    for i in range(low, high):
        if numbers[i] <= pivot:
            item = item + 1
            (numbers[item], numbers[i]) = (numbers[i], numbers[item])

    (numbers[item + 1], numbers[high]) = (numbers[high], numbers[item + 1])

    return item + 1

最初にピボット要素を選択します。ここではリストの末尾の値をピボットとしています。

次に、forループでリスト内のすべての要素を走査します。ある数値がピボット以下であればピボットの左側へ移動し、そうでなければ右側に配置されます。

この関数は新しい「high」の位置（item + 1）を返します。これがピボットの最終的な位置となります。

続いて、このアルゴリズムを実行するための別の関数を作成します。

def quick_sort(numbers, low, high):
    if low < high:
        pivot = prepare(numbers, low, high)

        quick_sort(numbers, low, pivot - 1)

        quick_sort(numbers, pivot + 1, high)

この関数は、まず「low」が「high」より小さいかどうかを確認します。小さい場合はソートを継続し、そうでなければ終了します。ソートが終了するということは、リストがすでに整列済みであることを意味します。

次に、prepare()メソッドを呼び出します。これによりピボットの位置が特定され、各要素が正しい場所へ移動されます。

その後、quick_sort()メソッドを2回呼び出します。1回目はピボットより左側の要素に対して、2回目はピボットより右側の要素に対してクイックソートを実行します。自分自身を呼び出しているため、この関数は再帰的であると言えます。

この処理は、リスト内のすべての要素がソートされるまで繰り返されます。

メインプログラムの作成

最後に、ソート対象のリストを定義するメインプログラムを書きましょう。

values = [8, 4, 5, 2, 1, 3]
total_values = len(values)

quick_sort(values, 0, total_values - 1)

print(values)

まず、ソート対象のリストを定義します。Pythonのlen()メソッドでリストの長さを取得し、quick_sort()メソッドを呼び出します。

引数には、ソートしたいリスト「values」、最小インデックスとして0、最大インデックスとして「values」の長さから1を引いた値を渡します。最大インデックスが「長さ - 1」になるのは、リストの最初の要素のインデックスが0だからです。

それでは、プログラムを実行してみましょう。

[1, 2, 3, 4, 5, 8]

コードは正しくソートされたリストを返しました！クイックソートは理解も実装も決して簡単ではありませんが、これで見事に完成です。

計算量の概要

平均的なケースでは、このアルゴリズムの計算量はO(n log n)になります。これは、ピボットが最大値・最小値ではなく、中央付近の値である場合に起こります。

クイックソートの最悪計算量はO(n²)です。これは、ピボットとして選んだ要素が最大値または最小値だった場合に発生します。この場合、ピボットは常にソート済み配列の端に位置することになり、無駄なサブ配列が大量に生成されてしまいます。

最良計算量はO(n log n)です。これは、ピボットが中央の要素と等しいか、中央付近にある場合に達成できます。

アルゴリズムの計算量についてさらに詳しく知りたい方は、ビッグオー記法（Big O Notation）に関するガイドも参考にしてください。

まとめ

Pythonのクイックソートは、再帰を使ってリストをより小さなリストに分解し、それぞれをソートするアルゴリズムです。各リストはピボット要素を基準にソートされ、ピボットより大きい要素は右側へ、小さい要素は左側へ移動されます。

本記事で紹介した手順とコード例を参考に、ぜひご自身でもクイックソートの実装に挑戦してみてください。