Pythonでクイックソート法(交換法)を実装する方法をソースコード付きで解説します。
【クイックソートとは】リストを昇順・降順ソート
クイックソート法は、リストの要素を整列(昇順・降順ソート)するアルゴリズムの1つです。
リスト内のデータから適当な軸要素(pivot)を選び、その軸要素を基準値(しきい値)としてデータ全体を2つのグループに分割します。そして、2つのグループそれぞれでまた基準値を選んでさらに分割し、それを繰り返すことで整列を行います。
このような「分割を繰り返して整列を行う」手法は分割統治法(Divide and conquer)ともいわれます。
– | クイックソートの特徴 |
---|---|
1 | バブルソートと比較して、データの比較と交換回数が少ない。 |
2 | ランダムに散らばっているデータに対して、最も高速に並べ替えができるため、 よく利用されている。 |
理解を深めるために、7つの要素をもつリスト[7, 3, 5, 6, 2, 1]の昇順ソートをクイックソート法で行ってみます。
リストの状態 | 操作 |
---|---|
[4, 7, 9, 5, 2, 1, 3] | 1番目の要素を軸要素(基準値)とする。 |
[2, 1, 3], [4], [7, 9, 5] | 軸要素(基準値:4)よりも大きい値と小さい値の2グループに分割する(大きいグループは軸要素の右側、小さいグループは左側に移動)。 |
[2, 1, 3], [4], [7, 9, 5] | それぞれのグループの先頭要素を軸要素(基準値)とする。 |
[1], [2], [3], [4], [5], [7], [9] | それぞれのグループで軸要素(基準値)よりも大きい値と小さい値の2グループに分割する。 |
[1, 2, 3, 4, 5, 7, 9] | これ以上グループに分割できないので、ソートを終了する。 |
参考 | 【クイックソート法とは】リストの昇順・降順ソートの原理と計算量 |
今回は、グループの先頭要素を軸要素としましたが、他にも「ランダムに要素を1つ選択」
「ランダムに要素を3つ選択し、その中央値を選択」「先頭と2番目の要素のうち、値が大きいほうを選択」するなど、軸要素の取り方は様々あります。
【サンプルコード】Python3
Python3でリストのバブルソートを行うサンプルコードです。
def quick_sort(arr):
# 左右2つに分割したデータを格納するリスト
left_arr = []
right_arr = []
# 要素数長が1以下なら終了
if len(arr) <= 1:
return arr
# 先頭要素を軸要素(基準値)に指定
pivot = arr[0]
pivot_count = 0
# 左右2つのグループに分割
for ele in arr:
if ele < pivot:
left_arr.append(ele)
elif ele > pivot:
right_arr.append(ele)
# 基準値と同じなら、その個数をカウント
else:
pivot_count += 1
# 左右2つに分割したリストに対して、再帰的に関数を呼び出して繰り返す
left_arr = quick_sort(left_arr)
right_arr = quick_sort(right_arr)
# ソートしたら分割したリストを結合(ピポッドはカウントされた個数だけ中央に挿入)
return left_arr + [pivot] * pivot_count + right_arr
# クイックソート1
arr = [2, 3, 7, 5]
print("ソート前:", arr)
sorted_arr = quick_sort(arr)
print("ソート後:", sorted_arr)
print("-----------")
# クイックソート2
arr = [9, 5, 8, 2, 8, 9, 7]
print("ソート前:", arr)
sorted_arr = quick_sort(arr)
print("ソート後:", sorted_arr)
"""
ソート前: [2, 3, 7, 5]
ソート後: [2, 3, 5, 7]
-----------
ソート前: [9, 5, 8, 2, 8, 9, 7]
ソート後: [2, 5, 7, 8, 8, 9, 9]
"""
– | 関連記事 |
---|---|
1 | Python版OpenCV入門 サンプル集 |
2 | 【画像処理入門】アルゴリズム&プログラミング |
コメント