#Pythonの強み
##リスト内包表記でクイックソート
quickSortSimple.py
data = [26,13,32,65,76,22,43,87,14,59]
def QuickSort(data):
if len(data) <= 1: # データが1個ならソートする必要ない
return data
# 基準となるデータ(ピボット)としてリストの先頭の値を使用
pivot = data[0]
# ピボット以上のデータでリスト作成
left = [ii for ii in data[1:] if ii >= pivot]
# ピボット未満のデータでリスト作成
right = [ii for ii in data[1:] if ii < pivot]
left = QuickSort(left) # 左側のソート
right = QuickSort(right) # 右側のソート
# ソート済みデータとピボットとを合わせて返す
return left + [pivot] + right
print(QuickSort(data))
# 結果
# [87, 76, 65, 59, 43, 32, 26, 22, 14, 13]
このたびもピボットとしてリスト先頭の値を使用しておりますが、最初の値、最後の値、適当に選んだ3つの値の中央値など、選択肢は様々で、よい値を選ぶことが早い処理の鍵のようです。
###・ソートに関する他の記事
クイックソート|大きい順
[マージソート|大きい順のソーティング]
(https://qiita.com/ProOJI/items/c34441886a9d60fc9664)
[選択ソート|備忘録]
(https://qiita.com/ProOJI/items/a7fc63c943f51a4e2e92)