クイックソート２｜リスト内包表記で簡単に

Pythonの強み

リスト内包表記でクイックソート

quickSortSimple.py

data = [26,13,32,65,76,22,43,87,14,59]

def QuickSort(data):
    if len(data) <= 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]

このたびもピボットとしてリスト先頭の値を使用しておりますが、最初の値、最後の値、適当に選んだ３つの値の中央値など、選択肢は様々で、よい値を選ぶことが早い処理の鍵のようです。

・ソートに関する他の記事

クイックソート｜大きい順
マージソート｜大きい順のソーティング
選択ソート｜備忘録