クイックソートは、様々なソートアルゴリズムの中でも、非常に高速でよく利用されている整列アルゴリズムです。この記事では、Pythonを用いてクイックソートの実装方法を紹介します。
クイックソートとは？
クイックソートは、リストから任意にデータを選択し、これを基準として小さい要素と大きい要素に分割し、それぞれのリストでまた同じような処理を繰り返してソートする方法です。基準となるデータをピボットと呼びます。
Pythonでのクイックソートの実装
以下に、Pythonでのクイックソートの実装例を示します。
def quick_sort(data):
if len(data) <= 1:
return data
pivot = data.pop(0)
left = [i for i in data if i <= pivot]
right = [i for i in data if i > pivot]
left = quick_sort(left)
right = quick_sort(right)
return left + [pivot] + right
if __name__ == '__main__':
DATA = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
print(f"{DATA} → {quick_sort(DATA)}")
このコードでは、リストの先頭をピボットとして取り出し、ピボットより小さいものでリストを作り、ピボットより大きいものでリストを作ります。そして、それぞれのリストに対して再帰的に同じ処理を行います。
クイックソートの計算量
クイックソートの計算量は、ピボットの選択がうまくいけば、マージソートと同様にO(n log n)となります。ただし、ピボットをうまく選ぶことができないと、最悪の場合、O(n^2)となります。
以上、Pythonでのクイックソートの実装方法について説明しました。このアルゴリズムを理解し、Pythonでの実装ができれば、より高度なアルゴリズムに挑戦するための一歩となるでしょう。.