クイックソート

/

クイックソートについて

タグ quick sort merge sort

概要

  • 計算量
    • 最悪値: O(n^2)
    • 平均: O(n log n)
    • 平均的にquick sortのほうがmerge sortより高速らしい
  • 手順
    • 基準となる一点を決める(ランダムでも先頭でも可)
    • 基準より大きい値、小さい値、等しい値に分割する
    • 大きい値のグループ、小さい値のグループを再帰でquick sortする
    • 出力を合成

視覚的な説明

コード

import random

def qsort(arr):
    # 基準のpivotよりも小さいグループ、同じグループ、大きいグループに分ける
    lesser, equal, greater = [], [], []
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr) # pivotを定義
    for x in arr:
        if x < pivot:
            lesser.append(x)
        elif x == pivot:
            equal.append(x)
        elif x > pivot:
            greater.append(x)
    return qsort(lesser) + equal + qsort(greater)

arr = [random.randint(0, 100) for _ in range(11)]
print(arr) # [50, 80, 84, 22, 9, 33, 49, 21, 87, 45, 55]
print(qsort(arr)) # [9, 21, 22, 33, 45, 49, 50, 55, 80, 84, 87]

google colab