クイックソートは人気のあるソートアルゴリズムで、マージソートと並んでよく使われるものです。
平均的な複雑さが O(nlogn) であることから、効率的なソートアルゴリズムの良い例と言えるでしょう。
その人気の一部は、実装の容易さにも由来している。
この記事の最初の部分では単純な整数を使用しますが、このアルゴリズムをカスタムクラスのオブジェクトをソートするために変更する方法を例として挙げます。
クイックソートは、分割統治型、インプレース型、不安定型の3種類のソートアルゴリズムの代表格である。
- 分割統治(Divide and conquer)。分割統治：配列をより小さな配列に分割し、最終的に空の配列、あるいは要素が1つしかない配列になるまで、より大きな配列を再帰的にソートします。
- インプレース。インプレース：クイックソートは、配列やその部分配列のコピーを作成しません。しかし、再帰的な呼び出しを行うため、スタックメモリを必要とします。
- 不安定。不安定：安定したソートアルゴリズムとは、同じ値を持つ要素が、ソートされる前の配列と同じ相対順序で現れるものです。不安定なソートアルゴリズムでは、このようなことは起こり得ますが、保証されません。
これは、プリミティブ型ではなくオブジェクトをソートするときに重要になるものです。
例えば、同じ「年齢」を持つ複数の Person オブジェクトがあるとします。
例えば、Dave が 21 歳で Mike が 21 歳だとします。
Dave と Mike を含むコレクションを年齢順にソートして Quicksort を使用する場合、アルゴリズムを実行するたびに Dave が Mike よりも先に来る保証はありませんし、その逆もまた然りです。
クイックソート
基本版のアルゴリズムは次のようになる。
擬似乱数の要素を取り、それをピボットとして使用することで、コレクションを2つの（ほぼ）等しい部分に分割する。
ピボットより小さい要素はピボットの左側に、大きい要素はピボットの右側に移動する。
この処理を、ピボットの左側のコレクションと、ピボットの右側の要素の配列に対して、配列全体がソートされるまで繰り返します。
要素を他の要素よりも「大きい」「小さい」と表現する場合、必ずしも整数の大小を意味するわけではなく、任意のプロパティでソートすることが可能です。
カスタムクラス Person があり、各人が name と age を持っているとすると、 name (辞書順) や age (昇順または降順) でソートすることができます。
クイックソートの仕組み
クイックソートは、多くの場合、配列を等分に分割することに失敗します。
これは、処理全体がピボットの選び方に依存しているからです。
ピボットは、要素の半分よりおおよそ大きく、残りの半分よりおおよそ小さくなるように選択する必要があります。
このプロセスは直感的に理解できるように思えますが、非常に難しいのです。
配列の適切なピボットをどのように選択するか、少し考えてみてください。
Quicksortの歴史の中で、ピボットの選択方法については多くのアイデアが提示されてきました。
ランダムに要素を選択する方法は、良いピボットの選択が保証されない一方で、ランダムな要素を選択することがいかに「高価」であるかという理由からうまくいきません。
最も単純な方法は、単純に最初の（または最後の）要素を選ぶことです。
これは、皮肉にも、すでにソートされた（あるいはほとんどソートされていない）配列に対して、クイックソートが非常に悪いパフォーマンスを発揮することにつながります。
この方法は簡単で、ピボットの選択は非常に効率的です（そして、繰り返し行う必要があります）。
さて、ピボットを選択したら、それをどうするか。
ここでも、パーティショニング自体にはいくつかの方法があります。
ピボットへの「ポインタ」と、「小さい」要素へのポインタ、「大きい」要素へのポインタを用意します。
目標は、ピボットより小さい要素がすべて左側に、大きい要素がすべて右側に来るように、要素を移動させることです。
小さい要素と大きい要素は必ずしもソートされる必要はなく、ピボットの適切な側に置くだけでよいのです。
次に、ピボットの左側と右側を再帰的に調べます。
これから行う予定の処理を順を追って説明します。
下図の配列を例にとると、最初の要素をピボット（29）とし、その直後から小さい要素（「low」と呼ぶ）へのポインタ、最後から大きい要素（「high」と呼ぶ）へのポインタを開始します。
- 29 は最初のピボットで、low は 99、high は 44 を指します。
29 | 99 (low),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44 (high)
- ピボットよりも低い値を見つけるまで、
highを左に移動します。
29 | 99 (低),27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21 (高),44
- high変数がピボットより小さい要素である21を指しているので、配列の先頭付近で入れ替え可能な値を探したいと思います。ピボットより小さい値と交換しても意味がないので、low が小さい要素を指している場合は、より大きい値を探してみます。
- ピボットより大きい要素が見つかるまで、変数lowを右に移動します。幸運なことに、low はすでに 99 に位置していました。
- lowとhighの場所を交換します。
29｜21（低）、27、41、66、28、44、78、87、19、31、76、58、88、83、97、12、99（高）、44。
- この直後に、highを左に、lowを右に移動します（21と99が正しい位置にあるため）。
- ピボットより低い値に達するまで、再び高値を左に移動します（すぐに見つかります） – 12
- 次に、低値を右に移動してピボットより大きい値を探します。
この処理は、最終的に low と high のポインタが 1 つの要素で出会うまで続けられます。
29｜21｜27｜12｜19｜28（低値/高値）｜44｜78｜87｜66｜31｜76｜58｜88｜83｜97｜41｜99｜44
- このピボットにはもう用はないので、ピボットとハイを入れ替えるだけで、この再帰的なステップは終了です。
28,21,27,12,19,29,44,78,87,66,31,76,58,88,83,97,41,99,44
ご覧のように、29より小さい値はすべて29の左側に、29より大きい値はすべて右側に配置することが実現しました。
このアルゴリズムは、次に28,21,27,12,19（左側）のコレクションと44,78,87,66,31,76,58,88,83,97,41,99,44（右側）コレクションについて同じことを行います。
実装
配列の並べ替え
入力配列をより小さな配列に分割し、要素をピボットの適切な側に移動させ、それを繰り返します。
いくつかの再帰的な呼び出しがどのように見えるか見てみましょう。
- 最初にアルゴリズムを呼び出すときは、インデックス0からn-1までのすべての要素を考慮します（nは配列の要素数）。
- ピボット位置がkであれば、0からk-1までとk+1からn-1までの要素について、この処理を繰り返します。
- k+1 から n-1 までの要素をソートしている間に、現在のピボットがある位置 p に到達してしまうので、k+1 から p-1、p+1 から n-1 までの要素をソートします。
そこで、ここでは2つの関数、 partition() と quick_sort() を利用することにします。
quick_sort()関数は、まずコレクションをpartition()` してから、分割された部分に対して再帰的に自分自身を呼び出します。
まずは partition() 関数から始めましょう。
def partition(array, start, end):
pivot = array[start]
low = start + 1
high = end
while True:
# If the current value we're looking at is larger than the pivot
# it's in the right place (right side of pivot) and we can move left,
# to the next element.
# We also need to make sure we haven't surpassed the low pointer, since that
# indicates we have already moved all the elements to their correct side of the pivot
while low <= high and array[high] >= pivot:
high = high - 1
# Opposite process of the one above
while low <= high and array[low] <= pivot:
low = low + 1
# We either found a value for both high and low that is out of order
# or low is higher than high, in which case we exit the loop
if low <= high:
array[low], array[high] = array[high], array[low]
# The loop continues
else:
# We exit out of the loop
break
array[start], array[high] = array[high], array[start]
return high
最後に、quick_sort()関数を実装してみましょう。
def quick_sort(array, start, end):
if start >= end:
return
p = partition(array, start, end)
quick_sort(array, start, p-1)
quick_sort(array, p+1, end)
この2つの関数が実装されていれば、単純な配列に対して quick_sort() を実行することができます。
array = [29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44]
quick_sort(array, 0, len(array) - 1)
print(array)
出力
[12, 19, 21, 27, 28, 29, 31, 41, 44, 44, 58, 66, 76, 78, 83, 87, 88, 97, 99]
このアルゴリズムは不安定なので、この2つの44が互いにこの順序であったという保証はありません。
もしかしたら、元々入れ替わっていたのかもしれません。
しかし、これは整数の配列ではあまり意味がありません。
カスタムオブジェクトの並べ替え
Pythonでカスタムオブジェクトをソートするために、このアルゴリズムを書き換える方法がいくつかあります。
つまり、 >, ==, <= などはクラスオブジェクトでも動作するので、実際にはアルゴリズムの実装を変更する必要はないでしょう。
もう一つの方法は、呼び出し元が我々のアルゴリズムにメソッドを提供し、それがオブジェクトの実際の比較に使用されるようにすることです。
このようにアルゴリズムを書き換えてカスタムオブジェクトで使用することは非常に簡単です。
しかし、アルゴリズムが安定していないことに注意してください。
まず、Personクラスから始めましょう。
class Person:
def __init__(self, name, age):
self.name = name
self.age = age
def __str__(self):
return self.name
これはとても基本的なクラスで、name と age という2つのプロパティを持っているだけです。
ここでは、ソートのキーとして age を使用したいと思います。
これは、ソートアルゴリズムにカスタムラムダ関数を提供することで実現できます。
しかし、その前に、この提供された関数がアルゴリズム内でどのように使用されるかを見てみましょう。
演算子 <= や >= を使って直接比較するのではなく、この関数を呼び出して、どの Person が年齢が高いかを判断しています。
def partition(array, start, end, compare_func):
pivot = array[start]
low = start + 1
high = end
while True:
while low <= high and compare_func(array[high], pivot):
high = high - 1
while low <= high and not compare_func(array[low], pivot):
low = low + 1
if low <= high:
array[low], array[high] = array[high], array[low]
else:
break
array[start], array[high] = array[high], array[start]
return high
def quick_sort(array, start, end, compare_func):
if start >= end:
return
p = partition(array, start, end, compare_func)
quick_sort(array, start, p-1, compare_func)
quick_sort(array, p+1, end, compare_func)
そして、これらのオブジェクトのコレクションをソートしてみましょう。
オブジェクトの比較はラムダを介して quick_sort に渡され、 age プロパティを実際に比較していることがわかります。
p1 = Person("Dave", 21)
p2 = Person("Jane", 58)
p3 = Person("Matthew", 43)
p4 = Person("Mike", 21)
p5 = Person("Tim", 10)
array = [p1,p2,p3,p4,p5]
quick_sort(array, 0, len(array) - 1, lambda x, y: x.age < y.age)
for person in array:
print(person)
出力は次のようになります。
Tim
Dave
Mike
Matthew
Jane
このようにアルゴリズムを実装することで、適切な比較関数さえ用意すれば、どんなカスタムオブジェクトでも使用することができます。
クイックソートの最適化
Quicksort が与えられた配列の “半分” を独立してソートすることを考えると、並列化には非常に便利な機能です。
配列のそれぞれの「半分」をソートする別々のスレッドを持つことができ、理想的にはソートに必要な時間を半分にすることができます。
しかし、Quicksort はピボットの選択が特に運が悪いと非常に深い再帰呼び出しスタックを持つことになり、並列化はマージソートの場合ほど効率的ではありません。
小さな配列のソートには、単純で非再帰的なアルゴリズムを使用することが推奨されます。
挿入ソートのような単純なものでも、小さな配列ではQuicksortよりも効率的です。
ですから、理想的には、部分配列の要素数が少ないかどうか（多くの勧告では10個以下）確認し、もしそうなら、代わりに挿入ソートでソートするのがよいでしょう。
クイックソートの一般的なバリエーションとして、マルチピボットクイックソートがあります。
これは、元の配列をn個の小さな配列に分割し、n-1個のピボットを使用するものです。
しかし、ほとんどの場合、ピボット数は2つだけで、それ以上は使いません。
面白いことに、デュアルピボットクイックソートは、より小さい配列の挿入ソートとともに、Java 7のソート実装で使用されていました。
結論
前述したように、クイックソートの効率はピボットの選択に大きく依存し、アルゴリズムの時間（とスタックスペース）の複雑さを「作るか壊すか」することができます。
また、アルゴリズムの不安定さは、カスタムオブジェクトを使用する際の問題点でもあります。
しかし、それでも、クイックソートの平均時間計算量は O(n*logn) であり、比較的低い空間使用量とシンプルな実装により、非常に効率的で人気のあるアルゴリズムとなっています。
もしもっと学びたいのであれば、他の記事、Sorting Algorithms in Pythonをご覧ください。
Pythonのソートアルゴリズムについてもっとカバーしていますが、それほど深くはありません。