クイックソートは、分割統治法の一種で、平均計算時間がO(n log n)と非常に効率的なソートアルゴリズムです。以下に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
このコードでは、まずリストの先頭をピボットとして選択します。次に、ピボットより小さい要素を左のリストに、ピボットより大きい要素を右のリストに分割します。そして、左と右のリストに対して再帰的に同じ処理を行います。
以下に、この関数を使用してリストをソートする例を示します。
data = [6, 15, 4, 2, 8, 5, 11, 9, 7, 13]
print(f"{data} → {quick_sort(data)}")
出力結果は以下の通りです。
[6, 15, 4, 2, 8, 5, 11, 9, 7, 13] → [2, 4, 5, 6, 7, 8, 9, 11, 13, 15]
このように、Pythonでクイックソートを実装することは非常に簡単です。ただし、ピボットの選択は重要で、うまく選ぶことができないと最悪の場合、計算量はO(n^2)となります。.