ソート（導入）

ソートはコーディング面接において頻繁に使われる概念です。某外資戦略系コンサルファームの面接にてソート関数をそのまま実装しろという問題を私は過去に一度だけ経験した事はあります。正直にいってそのまま丸暗記する事にあまり意味はありません。しかし、ソートアルゴリズムの特性や仕組みを知っておく事で、コーディング面接でのフォローアップでの会話についていく事ができます。

なぜクイックソートが$\mathrm{O(NlogN)}$の時間計算量でソートできるのか？なぜ最悪の場合に$\mathrm{O(N^2)}$の時間計算量になるのか？マージソートは何故安定ソートなのか？メモリをほぼ限界まで使用している巨大な配列に対してソートする場合にはどうすべきか？など普通に面接中に聞かれてもおかしくはありません。この章でしっかりと仕組みを理解し、そのまま丸暗記より導出できるようになっておきましょう。

バブルソート

バブルソートはシンプルなソートアルゴリズムです。隣接する要素を比較し、大きい（or 小さな）値が右側に来るように交換することで、リスト内の要素をソートします。

配列のサイズをnをし、昇順のソートの場合を考えます。ステップとしては

1. 最初のイテレーションでは、j=0からj=n-1まで隣接する要素a[j] > a[j+1]を比較して、条件が成立する場合要素を入れ替えることで、最大の要素が配列の最後に移動します。
2. 次のイテレーションでは、j=0からj=n-2まで同様のプロセスが繰り返され、次に大きい要素が配列の末尾から2番目に移動します。
3. このイテレーションを、全ての要素はソートされるまで繰り返します。

from typing import List


def bubble_sort(nums: List[int]) -> List[int]:
    n = len(nums)
    for i in range(n):
        for j in range(n-i-1):
                if nums[j] > nums[j+1]:
                    nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums


print(bubble_sort([6, 15, 4, 2, 8])) # Output: [2, 4, 6, 8, 15]

ソートの安定性

安定ソート とはキーが同等な複数のデータのソート前の前後関係がソート後も保存されるものの事を言います。バブルソートは等しい値の場合に要素が交換されないので安定ソートとなります。

時間計算量

上記のコードのバブルソートの最良、最悪、平均時間計算量は$\mathrm{O(N^2)}$です。これは、ネストされたfor文を使用して、配列の各要素が他のすべての要素と比較されるためです。

しかし、一度でも要素の交換が行われたのかを内側のループでフラグで管理する事で要素の入れ替えが行われなかった際にはその配列は既にソートされている事と見なしループをbreakでいち早く抜ける事ができるので、最良時間計算量を$\mathrm{O(N)}$にまで減らす事ができます。これはほぼソート済の配列に対して有効です。

空間計算量

バブルソートはin-placeアルゴリズムなので最良、最悪、平均空間計算量は$\mathrm{O(1)}$です。in-placeアルゴリズムとはデータ構造の変換を行うにあたって、追加のメモリ領域をほとんど使わずに行うアルゴリズムの事です。バブルソートはソートを行う際に元の配列に対して要素の交換を行います。

マージソート

マージソートは効率的なソートアルゴリズムです。分割統治法に基づいており、以下のステップで動作します。マージソートは再帰呼出しの知識を要します。前提知識のない方はRecursion / Backtracking（再帰呼び出し / バックトラック法）の序盤の説明を読む事をオススメします。

1. 分割 : リストを同じサイズの再帰的に2つのサブリストに分割していきます。

2. ソート: サブリストをソートします

3. 結合 : ソートされたサブリストをマージして、元のリストを再構築します 詳細を見ていきましょう。2つのソート済み配列を「マージ（併合）」して1つのソート済み配列を作る merge() 関数を活用します。配列のleft番目からright番目までをソートする merge_sort(nums, left, right ) のアルゴリズムは次です。

4. mid = (left + right) / 2 でサブリストに分割するポイントを決める

5. merge_sort(nums, left, mid)でleft番目からmid番目のサブリストをソート

6. merge_sort(nums, mid+1, right)でmid+1番目からright番目のサブリストをソート

7. merge(nums, left, mid, right) で整列済のソートした配列をマージ

from typing import List


def merge(nums: List[int], left: int, mid: int, right: int):
    # 並べ替えられた左右の半分を一時配列にコピー
    left_nums = nums[left:mid+1]
    right_nums = nums[mid+1:right+1]

    i, j, k = 0, 0, left  # left_nums、right_nums、numsのインデックス

    # 二つの並べ替えられた半分を元の配列に統合
    while i < len(left_nums) and j < len(right_nums):
        if left_nums[i] <= right_nums[j]:
            nums[k] = left_nums[i]
            i += 1
        else:
            nums[k] = right_nums[j]
            j += 1
        k += 1

    # left_numsとright_numsの残りの要素をコピー（あれば）
    while i < len(left_nums):
        nums[k] = left_nums[i]
        i += 1
        k += 1
    while j < len(right_nums):
        nums[k] = right_nums[j]
        j += 1
        k += 1


def merge_sort(nums: List[int], left: int, right: int) -> List[int]:
    # これ以上分割できない場合
    if left >= right:
        return nums

    # 配列の中間インデックス
    mid = (left + right) // 2

    # 左右の半分を再帰的に並べ替え
    merge_sort(nums, left, mid)
    merge_sort(nums, mid+1, right)

    # 並べ替えられた半分を統合
    merge(nums, left, mid, right)

    return nums


print(merge_sort([5, 2, 3, 2, 1], 0, 4))

ソートの安定性

マージソートは要素が等しい場合にそれらの元の順序を保持するため安定ソートです。このアルゴリズムは、分割されたサブリストをマージする際に、等しい要素が見つかった場合、常に先に分割された左側のサブリストの要素を選択します。これにより、等しい要素間の相対的な順序が変わらないため、マージソートは元の位置関係を保持する安定なソート方法となります。

時間計算量

マージソートの最良、最悪、平均時間計算量はすべて$\mathrm{O(NlogN)}$です。これは、どのような状況でもリストが毎回半分に分割され、各レベルで全要素がマージされるためです。

空間計算量

マージソートの最良、最悪、平均空間計算量はすべて$\mathrm{O(N)}$です。これは、ソート中に配列を分割し、その分割された部分をマージするために最終的に入力される配列と同じサイズの配列を確保するためです。

クイックソート

クイックソートはマージソート同様に分割統治法に基づくアルゴリズムで、効率的なソートアルゴリズムです。以下の手順で動作します。

1. Pivotの選択 : 配列内から一つの要素（Pivot）を選びます。このPivotの選び方には様々な方法がありますが、ランダムに選ぶ方法や配列の中央値を選ぶ方法などが一般的です。以下のコードではランダムに一つ選んでいます。
2. パーティション（分割） : Pivotより小さい要素を配列の左側に、Pivot以上の要素を配列の右側に移動させます。
3. 再帰的にソート : パーティションされたサブリストに対して、上記の手順を再帰的に適用します。 下の図では配列をPivotごとにパーティションに分割する手法を図で表したものです。最後の値の3がPivotだった場合を想定しています。

今回はより簡単なLomutoのパーティションをベースに解説しています。他にもHoareのパーティションなどもあります。比較はこちらをご覧ください。

このパーティションによりパーティションの左側にはPivotよりの要素が並び、右側にPivot以上の要素が並びます。これはnums[j] < pivot_valueの時に左側にnums[j]の要素を移動させているからです。

ソートの全体図を書くと

from typing import List
import random


def partition(nums: List[int], left: int, right: int):
    # Pivotをランダムに選択する
    pivot_index = random.randint(left, right)
    pivot_value = nums[pivot_index]
    # Pivotをリストの最後に移動する
    nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
    i = left

    # リストをパーティションに分ける
    for j in range(left, right):
        if nums[j] < pivot_value:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

    # Pivotを正しい位置に移動する
    nums[i], nums[right] = nums[right], nums[i]
    return i # Pivotの位置を返す


def quick_sort(nums: List[int], left: int, right: int):
    if left >= right:
        return
    mid = partition(nums, left, right)
    quick_sort(nums, left, mid-1)
    quick_sort(nums, mid+1, right)


nums = [5, 2, 1, 4, 3]
quick_sort(nums, 0, len(nums)-1)
print(nums) #　Output: [1, 2, 3, 4, 5]

ソートの安定性

クイックソートは 不安定なソート です。これは、Pivotを基準に要素を分割する過程で、等しい値の要素の相対的な順序が変わる可能性があるためです。例えば、配列内に等しい値の要素が複数ある場合、これらの要素がソート後に元の順序を維持する保証はありません。

時間計算量

クイックソートの時間計算量は、最悪の場合には$\mathrm{O(N^2)}$ですが、最良・平均時間計算量では $\mathrm{O(NlogN)}$ です。

最悪のケースは、Pivotが毎回最小値または最大値になる場合に発生します。例えば以下のケースで考えてみましょう。毎回最大値をPivotとして選択するとN回の分割が行われ、N + (N - 1) + (N -2) + 2 + 1の比較が行われるので時間計算量は$\mathrm{O(N^2)}$となります。導出過程は1からNまでの和の公式を調べてみてください。

しかし、一般的にはPivotの選択が適切であれば、パーティションが均等に分割されるため、平均的なケースの時間計算量が $\mathrm{O(NlogN)}$ になります。

空間計算量

クイックソートはin-placeアルゴリズムなので最良、最悪、平均空間計算量はすべて$\mathrm{O(1)}$です。なお、再帰におけるコールスタックを考えると最悪$\mathrm{O(N)}$となります（コールスタックの深さが愛作Nになるので）。