クイックソートは、分割統治（Divide and Conquer）の方針に従ったソートアルゴリズムです。
ピボットとなる要素を選び、その周囲にスワップを行いながら要素を配置していくという考え方で動作します。
配列がソートされるまで、この処理を再帰的に繰り返します。
この記事では、QuickSortの仕組みと、その実装のためのPythonコードの書き方について学びます。
この記事もチェック：Pythonによるバブルソートの昇順、降順の実装方法とコードを解説する
QuickSort アルゴリズムを理解する
配列に対してクイックソートを実行する際の最初のステップは、ピボット要素を選択することです。
ピボット要素を選択する方法はさまざまです。
ランダムな要素を選択することもできますし、配列の中央値を選択することもできます。
ここでは、簡単のために、配列の最初の要素をピボット要素として選択することにします。
1. ピボットエレメントの選択
上述したように、最初の要素がピボット要素として選ばれます。
pivot = array[start]
|
ピボットとなる要素を選んだら、その周りの要素を並べ替えます。
ピボットより小さい要素が左側、大きい要素が右側になるように要素を並べ替えます。
その方法は？
それは、次に説明します。
2. ピボットを中心とした要素の並べ替え
ピボットを中心に要素を並べ替えるには、2つの変数を初期化します。
これらの変数を low と high と呼ぶことにします。
low は配列の 2 番目の要素（ピボットの 1 つ後の要素）、high は配列の最後の要素で初期化されます。
low = start + 1
high = end
|
要素を並べ替えるには、lowを右へ、highを左へ移動させます。
このとき、ピボットより大きな値はすべて右側に、小さな値はすべて左側に移動するようにします。
このように値を並べると、ピボットより小さい要素はすべて左側にあり、大きい要素はすべて右側にあるので、並べ替えられた配列の中でピボット要素の最終的な位置が分かります。
ピボットの右側と左側の要素は、ソートされて配置される場合とされない場合があります。
3. 3. 安値と高値を移動させる方法は？
高値がpivotより小さい値を指すまで、または高値が低値より小さくなるまで、高値を左方向に移動させます。
while low <= high and array[high] >= pivot:
high = high - 1
|
同様に、pivot よりも高い値を指すようになるまで、または high が low よりも小さくなるまで、low を右方向に動かします。
while low <= high and array[low] <= pivot:
low = low + 1
|
ループを抜けた後、low が high よりも小さいか等しいかどうかを調べます。
もしそうなら、high と low の値を入れ替える必要があります。
if low <= high:
array[low], array[high] = array[high], array[low]
|
lowがhighより大きい場合、ループを抜け出し、highをピボットエレメントの位置として返します。
これは、ピボットを中心に値をうまく並べたことを意味します。
4. これまでの実装コード
ピボット要素を選択し、要素を並べ替える関数の完全なコードは以下の通りです。
def pivot(array, start, end):
#initializing pivot = array[start]
low = start + 1
high = end
while True:
#moving high towards left while low <= high and array[high] >= pivot:
high = high - 1
#moving low towards right while low <= high and array[low] <= pivot:
low = low + 1
#checking if low and high have crossed if low <= high:
#swapping values to rearrange array[low], array[high] = array[high], array[low]
else:
#breaking out of the loop if low > high break
#swapping pivot with high so that pivot is at its right # #position array[start], array[high] = array[high], array[start]
#returning pivot position return high
|
5. 5. 配列の 2 つの部分に対して再帰呼び出しを実行する
ピボットの周囲で要素を並べ替えたら、配列の半分に対して再帰呼び出しを行う必要があります。
これらの呼び出しは、サイズが 1 の配列ができるまで繰り返されます。
再帰呼び出しを行う関数のコードは以下のとおりです。
def quick_sort(array, start, end):
if start >= end:
return
#call pivot p = pivot(array, start, end)
#recursive call on left half quick_sort(array, start, p-1)
#recursive call on right half quick_sort(array, p+1, end)
|
最後の2つの文は、それぞれ左半分と右半分に対して再帰的な呼び出しを行います。
ピボットの選択とその周りの要素の並べ替えは、左半分と右半分で同じように繰り返されます。
この処理を繰り返すことで、各要素が正しい位置に配置されていることを確認します。
ここでいう「正しい位置」とは、小さい要素はすべて左側に、大きい要素はすべて右側にあることを意味します。
すべての要素が正しい位置に配置されると、ソートされた配列ができあがります。
クイックソート配列の例
コードをテストするための例を挙げてみましょう。
[5,1,3,9,8,2,7] |
再帰呼び出しのたびに、配列のピボット要素、左半分、右半分を表示するコードを追加しましょう。
def quick_sort(array, start, end):
if start >= end:
return
p = pivot(array, start, end)
print("Pivot",array[p])
print("left :", array[start:p])
print("right :",array[p+1:end+1])
print(")
quick_sort(array, start, p-1)
quick_sort(array, p+1, end)
|
上記のサンプル配列でコードを実行してみましょう。
array = [5,1,3,9,8,2,7]
quick_sort(array, 0, len(array) - 1)
print(array)
|
出力は次のようになります。
Pivot 5left : [2, 1, 3]right : [8, 9, 7]Pivot 2left : [1]right : [3]Pivot 8left : [7]right : [9][1, 2, 3, 5, 7, 8, 9] |
ピボット要素ごとに、左の配列にはピボットより小さい要素、右の配列にはピボットより大きい要素が含まれることがわかります。
この再帰呼び出しを視覚的に表現すると、次のようになります。
def pivot(array, start, end):
#initializing pivot = array[start]
low = start + 1
high = end
while True:
#moving high towards left while low <= high and array[high] >= pivot:
high = high - 1
#moving low towards right while low <= high and array[low] <= pivot:
low = low + 1
#checking if low and high have crossed if low <= high:
#swapping values to rearrange array[low], array[high] = array[high], array[low]
else:
#breaking out of the loop if low > high break
#swapping pivot with high so that pivot is at its right # #position array[start], array[high] = array[high], array[start]
#returning pivot position return high
def quick_sort(array, start, end):
if start >= end:
return
#call pivot p = pivot(array, start, end)
#recursive call on left half quick_sort(array, start, p-1)
#recursive call on right half quick_sort(array, p+1, end)
array = [5,1,3,9,8,2,7]
quick_sort(array, 0, len(array) - 1)
print(array)
|
完全実装
クイックソートの完全な実装は以下の通りです。
まとめ
この記事では、PythonでQuicksortを実装することについて述べました。
Quicksort の最悪の場合の時間計算量は O(n2) であり、平均の場合の時間計算量は O(n logn) です。