エンジニア実践的基礎: クイックソート

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

クイックソートとは

クイックソートは名前の通り高速なソートアルゴリズムです。クイックソートはある値(ピボット)より小さなグループと大きなグループに分けて、それぞれのグループで再帰的に同じ処理を繰り返します。マージソート同様にカードで説明します。

あなたは ３・２・１・6・４ の数が書かれたカードを持っています。最初に４のカードを取り出して別の場所におきます。次に、左端から順番に４より小さい数は左側に、4より大きな数は右側におきます。言葉よりイラストの方がわかりやすいと思うので、以下のイメージを確認してください。

マージソートは「分割→ソート」なのに対しクイックソートは「ソート→分割」です。

他にもマージソートは追加のメモリを必要とするのに対し、クイックソートは必要としません。これを「インプレースアルゴリズム」とも呼びます。

実装

def quickSort(arr: list[int], s: int, e: int) -> list[int]:
    if e - s + 1 <= 1:
        # ベースケース
        return arr

    pivot = arr[e]
    left = s

    # ピボットより小さい値は左側に移動
    for i in range(s, e):
        if arr[i] < pivot:
            tmp = arr[left]
            arr[left] = arr[i]
            arr[i] = tmp
            left += 1

    # ピボットと終了時のインデックスの値を交換
    # left にはピボット以上の値が入るから右側に移動する
    arr[e] = arr[left]
    arr[left] = pivot
    
    # ピボットより左側を再帰処理
    quickSort(arr, s, left - 1)

    # ピボットより右側を再帰処理
    quickSort(arr, left + 1, e)

    return arr

計算量

マージソート同様に、分割するので、時間計算量は平均で O(nlogn) です。しかし、最大・最長の値をピボットに選択し続けると、常に左右にグループが偏るので毎回 O(n) の操作が必要になります。つまり n 回 O(n) を繰り返すので、最悪のケースで O(n^2) になります。これはマージソートとの大きな違いです。

空間計算量は、インプレースで追加のメモリを必要としないので、平均して階層分の O(logn) です。階層についてはマージソートを確認してください。最悪ケースでは、時間計算量同様に、常に最小・最大の値をピボットに選択するケースで、階層が分散されず n 層になってしまうので O(n) です。