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

Pythonでクイックソート法（交換法）を実装する方法をソースコード付きで解説します。

## 【クイックソートとは】リストを昇順・降順ソート

クイックソート法は、リストの要素を整列（昇順・降順ソート）するアルゴリズムの１つです。

リスト内のデータから適当な軸要素（pivot）を選び、その軸要素を基準値（しきい値）としてデータ全体を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つ選択し、その中央値を選択」「先頭と２番目の要素のうち、値が大きいほうを選択」するなど、軸要素の取り方は様々あります。

## 【サンプルコード】Python3

Python3でリストのバブルソートを行うサンプルコードです。

def quick_sort(arr):
    # 左右２つに分割したデータを格納するリスト
    left_arr = []
    right_arr = []

    # 要素数長が１以下なら終了
    if len(arr) <= 1:
        return arr

    # 先頭要素を軸要素（基準値）に指定
    pivot = arr[0]
    pivot_count = 0

    # 左右２つのグループに分割
    for ele in arr:
        if ele < pivot:
            left_arr.append(ele)
        elif ele > pivot:
            right_arr.append(ele)
        # 基準値と同じなら、その個数をカウント
        else:
            pivot_count += 1

    # 左右２つに分割したリストに対して、再帰的に関数を呼び出して繰り返す
    left_arr = quick_sort(left_arr)
    right_arr = quick_sort(right_arr)

    # ソートしたら分割したリストを結合（ピポッドはカウントされた個数だけ中央に挿入）
    return left_arr + [pivot] * pivot_count + right_arr


# クイックソート１
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]
"""