Cプログラマへの道 #12 - ソートアルゴリズム

このブログ記事では、いくつかのソートアルゴリズムとそのC言語での実装を紹介します。

プログラマーは幾度となく配列をソートする（大小で並び替える）機会に直面します。そのため、今回の記事ではいくつかのソートアルゴリズムとそのC言語での実装を紹介します。実装を見る前に、自分で一度実装に挑戦してみることをお勧めします。

バブルソート

バブルソートは比較的簡単なソートアルゴリズムで、配列の隣接する各要素を比較し、最も大きな要素を右端のインデックスに移動させることで、右から左に向かってソートされた配列を作成するというものです。

以下がC言語でのバブルソートの実装です：

void bubbleSort (int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; i < size - i - 1; i++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp; 
            }
        }
    }
};

このアルゴリズムは、イテレーションでスワップが発生しなかった場合に停止するよう最適化することができます。（試してみて下さい。）空間計算量は $O(1)$ で、各時点で要素のペアのみを処理するため、時間計算量は $O(n^2)$ です。なぜなら、平均して $\frac{n}{4}$ ペアをn回チェックする必要があるからです。（「バブルソート」という名前は、最も大きな要素が配列の上部（右側）にバブルのように浮かび上がる様子から来ていると勝手に推測しています。）

挿入ソート

もう一つの直感的なソートアルゴリズムは挿入ソートです。これは、各要素を通過して、左側の部分配列に適切な場所を見つけて挿入します。バブルソートとは異なり、右から左にソートするのではなく、左から右にソートします。

以下がC言語での挿入ソートの実装です：

void insertionSort (int arr[], int size) {
    for (int i = 0; i < size; i++) {
        int j = i - 1;
 
        while (j >= 0 && arr[j] > arr[i]) {
            arr[j + 1] = arr[j]; // シフトさせる
            j--;
        }
        arr[j + 1] = arr[i];
    }
}

ソートされていると仮定される左側の各要素をチェックし、現在の値を挿入する場所が見つかるまで要素を右にシフトします。バブルソートと同様に、挿入ソートの空間計算量は $O(1)$ で、時間計算量は $O(n^2)$ です。なぜなら、平均して $\frac{n}{4}$ ペアをn回チェックする必要があるからです。ただし、データがほぼソートされている場合、このwhileループは少ない回数しか実行されないため、とり素早く動作できます。

選択ソート

挿入ソートと似た戦略を持つもう一つのソートアルゴリズムは選択ソートです。現在の要素を挿入する場所を決定するために左側の部分配列を通過する代わりに、右側の部分配列から最小の要素を選択し、それを左側のソートされた部分配列の右端に配置します。

以下がC言語での選択ソートの実装です：

void selectionSort (int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int min = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] > arr[min]) {
                min = j;
            }
        }
        if (min != i) {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

上記の2つのソートアルゴリズムと同様に、選択ソートの空間計算量は $O(1)$ 、時間計算量は $O(n^2)$ です。なぜなら、平均して $\frac{n}{4}$ ペアをn回チェックする必要があるからです。何らかの理由でスワップ操作がコストのかかる場合、他の2つのアルゴリズムと比較してスワップ回数が少ないため、選択ソートが好まれることがあります。

マージソート

上記のソートアルゴリズムはすべて時間計算量が $O(n^2)$ であり、大規模な配列に対しては実用的ではありません。しかし、マージソートは分割統治法(divide and conquer)を使用するため、より高速です。これは、配列をより小さな部分配列に分割し、その後、それらの部分配列内の各要素を比較して結合することで機能します。たとえば、配列{2, 1, 4, 3}をソートする場合、最初に{2, 1}と{4, 3}に分割し、それをさらに分割して各部分配列が1つの要素だけになるまで分割します。

{2, 1, 4, 3} -> {2, 1}, {4, 3} -> {2}, {1}, {4}, {3}.

次に、各配列内の最小の要素を比較して選択し、配列を結合(マージ)します。

{2}, {1}, {4}, {3} -> {1, 2}, {3, 4} -> {1, 2, 3, 4}.

以下が、C言語でのマージソートの実装です：

void merge (int arr[], int l, int m, int r) {
    // 左配列と右配列をインデックスから作成
    int lArr[m - l + 1];
    int rArr[r - m];
 
    for (int i = 0; i < m - l + 1; i++) {
        lArr[i] = arr[l + i];
    }
    for (int j = 0; j < r - m; i++) {
        rArr[j] = arr[m + 1 + j];
    }
 
    // lArrまたはrArrの小さい要素を挿入
    int i = 0;
    int j = 0;
    int insertedUntil = l;
 
    while (i < m - l + 1 && j < r - m) {
        if (lArr[i] < rArr[j]) {
            arr[insertedUntil] = lArr[i];
            i++;
        } else {
            arr[insertedUntil] = rArr[j];
            j++;
        }
        insertedUntil++;
    }
 
    // 残りの要素を挿入
    while (i < m - l + 1) {
        arr[insertedUntil] = lArr[i];
        i++;
        insertedUntil++;
    }
 
    while (j < r - m) {
        arr[insertedUntil] = rArr[j];
        j++;
        insertedUntil++;
    }
}
 
void mergeSort (int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2 // 整数オーバーフローを防ぐため
 
        // 再帰呼び出し
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
 
        merge(arr, l, m, r);
    }
}

時間計算量を理解するために、配列がどれくらいの回数で分割され、mergeが呼び出されるかを考えます。分割の回数 $s$ は配列のサイズに関連し、 $n = 2^s$ という関係があるため、 $s = \log_2(n)$ となります。分割の回数は要素数が増えるにつれて対数的に増加します。各分割ごとに、mergeは2つの部分配列を結合し、各要素を通過して比較しますので、時間計算量は線形時間 $O(n)$ です。 $O(n)$ の操作が $O(\log n)$ 回行われるため、マージソートの時間計算量は $O(n \log n)$ であり、他のソートアルゴリズムよりも大幅にスケールが良くなります。

マージソートの欠点は、その空間計算量です。各マージ時に左と右の部分配列のコピーを作成する必要があり、そのために $O(n)$ の空間が必要です。しかし、メモリは比較的安価であり、マージソートは簡単に並列化できるため（これについては次の記事で取り上げます）、マージソートが好まれることが多いです。

クイックソート

クイックソートは説明が最も難しいアルゴリズムの一つですが、できる限りわかりやすく説明します。クイックソートは、ピボット要素を選び（ランダムに、または最後の要素）、他のすべての要素をピボットと比較し、ピボットより小さい要素を左に、それ以外の要素を右に配置するというプロセスです。このプロセスは、ピボットの左と右のより小さな部分配列（パーティション）に対して再帰的に繰り返され、各パーティションが1つまたは0の要素になるまで続けられます。

パーティションを作成する際には、特定のルールに従って動くiとjという2つのポインタを使用します。最初に、iは-1に設定され、jは0に設定されます。jをインクリメントしていき、配列のj番目の要素がピボットより小さい場合、iを右に1ステップ移動（1増加）させ、j番目の要素とi番目の要素をスワップします。そうでない場合は何もせず、jをインクリメントします。これにより、iの左側にあるすべての要素がピボットより小さくなることが保証されます。

jが最後のピボットに達したとき、i+1番目の要素とピボットをスワップします。これにより、ピボットの左側にはピボットより小さい値が含まれ、右側にはピボットより大きい値が含まれるパーティションが保証されます。(紙で試してみて下さい。)

以下が、C言語でのクイックソートの実装です：

// これは2つのスライドウィンドウを使用してパーティションを作成し、ピボットのインデックスを返します
int partition (int arr[], int l, int r) {
    int pivot = arr[r]; // 新しいピボットを選択
    int i = l - 1;
 
    // iとjをルールに従って移動
    for (int j = l; j < r - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
 
    int temp = arr[i + 1];
    arr[i + 1] = arr[r];
    arr[r] = arr[i + 1];
 
    return i + 1;
}
 
void quickSort (int arr[], int l, int r) {
    if (l < r) {
        int pivot = partition(arr, l, r);
 
        quickSort(arr, l, pivot - 1);　// 左側のパーティション
        quickSort(arr, pivot + 1, r); // 右側のパーティション
    }
}

この実装では、新しい配列を作成せずにソートを行う（インプレースソート）ため、平均的な空間計算量は $O(1)$ です。ピボットが中央値に近い値である場合、元の配列のおおよそ半分のサイズでパーティションを作成し続けることができます。そのため、マージソートと同様に、最良および平均の場合の時間計算量は $O(n \log n)$ です。（各パーティションに対してiとjを使用して一度だけ走査するため、各時間計算量は $O(n)$ です。）

ただし、配列がすでにソートされている場合や逆順にソートされている場合を考えてみてください。このような場合、ピボットは常に最大または最小の要素となり、パーティションをn回行う必要があります。したがって、最悪の場合、空間計算量は再帰スタックスペースによって $O(n)$ になり、時間計算量は $O(n^2)$ になります。このため、ランダムなピボットが使用されることが多いです。これは配列の初期順序に関係なく、連続して最悪のピボットをランダムに選択する確率は非常に低いためです。

まとめ

以上をまとめると、すべてのソートアルゴリズムの空間および時間計算量は次のようになります。

ソートアルゴリズムの空間および時間計算量
アルゴリズム	空間計算量	時間計算量
バブルソート	$O(1)$	$O(n^2)$
挿入ソート	$O(1)$	$O(n^2)$
選択ソート	$O(1)$	$O(n^2)$
マージソート	$O(n)$	$O(nlog(n))$
クイックソート	$O(1)$ (Worst: $O(n)$ )	$O(nlog(n))$ (Worst: $O(n^2)$ )

アルゴリズムによっては、すべてのケースで他のアルゴリズムよりも優れているものもありますが、配列のサイズや他の要因に応じて、別の最適なアルゴリズムを選択することが考えられます。たとえば、配列が小さく、すでにほぼソートされていると予想される場合、挿入ソートを選ぶべきかもしれません。そのため、さまざまなソリューションをテストし、特定の状況でどれを使用するかを決定することが重要です。また、異なるデータ構造の特性を活用するソートアルゴリズム（ヒープソートなど）も存在し、これについては今後の記事で取り上げる予定です。