クイックソートとはデータの集合をある決まりに従って並び替えるソートアルゴリズムの一種です。クイックソートはクイックと付いているだけあって早く処理できる方法になります。
今回は
array = [5,4,6,9,2,7,8,1,3] → array = [1,2,3,4,5,6,7,8,9]
arrayの中身をリストを数字の小さい順に並び替えるクイックソートを考えます。
ちなみにもしリスト型のメソッドを使うなら array.sort() で小さい順に並び変わります。
アルゴリズム
簡単にまとめると
基準値を決めてそれより小さいグループと大きいグループに分ける、小さいグループはさらに小さいグループとそれよりは大きいグループに分け、大きいグループはさらに大きいグループとそれよりは小さいグループに分けていく。それを繰り返して、グループの要素が一個になるまで行い、その全てのグループを連結し直すと並び替えられたリストになっている。
リストを分割(quicksort 関数)
１、元与えられたリストでPartition関数を呼び出して分割する
２、分割された左側(数が小さい方)と右側(数が大きい方)でまた別々にPartition関数を呼び出す。
３、２番がリストの要素の数が１つになる手前まで繰り返される(if l>rの条件)
リストを並び替え(Partition 関数)
１、pivotというデータの大小を比べる基準になる変数をソートするリストの中から決定します。
リストの最初や真ん中、最後のデータかリストのはじめのデータをpivotとしていたり、任意の３つのデータのメジアンをpivotとしているコードもみたことがあります。
２、pivotより左側のデーったはpivotのそれより小さく、右側のデータはpivotのそれより大きいことをループを使ってチェックしていきます。
３、左側のデータの方が大きかったり、右側の方が小さかった場合、それら二つをスワッピング（交換）します。
４、３の操作の終わったリストを[pivotとそれより前の要素を含むリスト]、[pivott以降の用を含むリスト]の二つに分割して、再帰させ１−３をまた繰り返されます。
最後に要素が１つしかないリストになるまで繰り返されます。
コード
def quicksort(arr):
qs(arr, 0, len(arr) - 1)
def qs(arr, l, r):
if l >= r:
return
p = partition(arr, l, r)
qs(arr, l, p - 1)
qs(arr, p + 1, r)
def partition(arr, l, r):
print("arr",arr[l:r+1])
pivot = arr[r]
print("pivot is", pivot)
i = l - 1
for j in range(l, r):
if arr[j] < pivot:
print("In-Small", arr[j])
i += 1
print("Swap point", i)
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[r] = arr[r], arr[i + 1]
return i + 1
a1 = [5, 4, 6, 9, 2, 7, 8, 1, 3]
quicksort(a1)
実行結果とその解説
実行結果
arr [5, 4, 6, 9, 2, 7, 8, 1, 3]
pivot is 3
In-Small 2
Swap point 0
In-Small 1
Swap point 1
arr [2, 1]
pivot is 1
arr [9, 5, 7, 8, 4, 6]
pivot is 6
In-Small 5
Swap point 3
In-Small 4
Swap point 4
arr [5, 4]
pivot is 4
arr [8, 9, 7]
pivot is 7
arr [9, 8]
pivot is 8
解説
１個目の分割と並び替え
arr [5, 4, 6, 9, 2, 7, 8, 1, 3]
pivot is 3
In-Small 2
Swap point 0
In-Small 1
Swap point 1
まだ分割する前なので、与えられた配列は一番最初のリストそのものです。
pivot(大小を比べる基準の数)は一番右の３が選ばれ、３以下の1,2は左のインデックス０と１の場所の値(5,4)と交換させられます。(arr[i], arr[j] = arr[j], arr[i])
そして最後にpivotの３を交換した次の値(インデックス２)に配置して1つ目の分割は終わります。( arr[i + 1], arr[r] = arr[r], arr[i + 1])
リストの分かれ方は以下になります。
[2,1] | 3 | [9,5,7,8,4,6]
２個目の分割と並び替え
arr [2, 1]
pivot is 1
1つ目の分割の結果の左側が最初再帰にかけられます。
pivotは一番右の1が選ばれますが、1がリストの中で一番小さいため交換は起こらず、pivotと先頭の数が交換させられます。
リストの分かれ方は以下になります。
1 | [2]
3つ目の分割と並び替え
arr [9, 5, 7, 8, 4, 6]
pivot is 6
In-Small 5
Swap point 3
In-Small 4
Swap point 4
1つ目の分割の結果の右側が再帰にかけられています。
pivotは一番右の6が選ばれます。5と4が6より小さいため、リストのインデックス3,4に小さい数が集められ、pivotより小さいグループ、pivot、pivotより大きいグループに分けられます。
＊arrは常に要素全体を持ったリストであり、rとlの引数でインデックスを操作して左右を分割しているため、この3つ目の分割と並び替えは前回のリストの右側に当たるため、[1,2,3,〇,〇]の○に該当する場所が数を入れ替える場所になります。
リストの分かれ方は以下になります。
1 | [2] | 3 | [5,4] | 6 | [8,9,7]
４、５つ目の分割と並び替え
arr [5, 4]
pivot is 4
arr [8, 9, 7]
pivot is 7
これらは先ほどの結果の [5,4] と[8,9,7]をさらに並び替え＆分割している様子になります。
２番目の分割と並び替えと全く同じことが行われているので分かりやすいかと思います。
リストの分かれ方は以下になります。
1 | [2] | 3 | 4 | [5] | 6 | 7 |[9,8]
６つ目の分割と並び替え
arr [9, 8]
pivot is 8
[9,8]のリストを並び変え＆分割を行っております。
リストの分かれ方は以下になります。
1 | [2] | 3 | 4 | [5] | 6 | 7 | 8 | [9]
これにより、1~9まで順番に並んだことになります。
参考文献
英語ですが、図と実際のコードを動画で解説しておりとても分かりやすくておすすめです。
A Complete Overview of Quicksort (Data Structures & Algorithms #11) - YouTube
