【Python】クイックソート法(交換法)を実装【分割統治法】

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 【画像処理入門】アルゴリズム&プログラミング

コメント