C#で再帰を使ってクイックソートを実装する方法

クイックソートとは

クイックソート（Quick Sort）は、分割統治法を用いた代表的なソートアルゴリズムです。配列から基準となる要素（ピボット）を選び、そのピボットを正しい位置に配置します。その後、ピボットの左側と右側の部分配列に対して再びクイックソートを適用し、これを配列全体が整列されるまで繰り返します。

この処理は再帰呼び出しによって自然に実装できるため、クイックソートは再帰の学習例としてもよく使われています。

C#での実装例

以下は、C#で再帰を利用してクイックソートを実装したプログラムの完全なコードです。

using System;
namespace QuickSortDemo {
    class Example {
        static public int Partition(int[] arr, int left, int right) {
            int pivot;
            pivot = arr[left];
            while (true) {
                while (arr[left] < pivot) {
                    left++;
                }
                while (arr[right] > pivot) {
                    right--;
                }
                if (left < right) {
                    int temp = arr[right];
                    arr[right] = arr[left];
                    arr[left] = temp;
                } else {
                    return right;
                }
            }
        }
        static public void quickSort(int[] arr, int left, int right) {
            int pivot;
            if (left < right) {
                pivot = Partition(arr, left, right);
                if (pivot > 1) {
                    quickSort(arr, left, pivot - 1);
                }
                if (pivot + 1 < right) {
                    quickSort(arr, pivot + 1, right);
                }
            }
        }
        static void Main(string[] args) {
            int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
            int n = 10, i;
            Console.WriteLine("Quick Sort");
            Console.Write("Initial array is: ");
            for (i = 0; i < n; i++) {
                Console.Write(arr[i] + " ");
            }
            quickSort(arr, 0, 9);
            Console.Write("\nSorted Array is: ");
            for (i = 0; i < n; i++) {
                Console.Write(arr[i] + " ");
            }
        }
    }
}

実行結果

上記プログラムを実行すると、次のような出力が得られます。

Quick Sort
Initial array is: 67 12 95 56 85 1 100 23 60 9
Sorted Array is: 1 9 12 23 56 60 67 85 95 100

プログラムの解説

ここからは、プログラムの各部分がどのように動作しているのかを順に見ていきましょう。

Main() メソッドの処理

Main() メソッドでは、まず初期状態の配列をコンソールに表示します。その後、quickSort() メソッドを呼び出して、配列に対してクイックソートを実行します。最後に、ソート後の配列を表示しています。

int[] arr = {67, 12, 95, 56, 85, 1, 100, 23, 60, 9};
int n = 10, i;
Console.WriteLine("Quick Sort");
Console.Write("Initial array is: ");
for (i = 0; i < n; i++) {
    Console.Write(arr[i] + " ");
}
quickSort(arr, 0, 9);

quickSort() メソッドの処理

quickSort() メソッドは、Partition() メソッドを呼び出してピボット要素を決定します。戻り値として得られたピボットの位置に応じて、左側の部分配列と右側の部分配列に対してそれぞれ quickSort() を再帰的に呼び出します。

if (left < right) {
    pivot = Partition(arr, left, right);
    if (pivot > 1) {
        quickSort(arr, left, pivot - 1);
    }
    if (pivot + 1 < right) {
        quickSort(arr, pivot + 1, right);
    }
}

条件 if (left < right) により、要素数が1以下になった部分配列ではそれ以上の分割を行わず、再帰が終了します。これが再帰の終了条件（ベースケース）です。

Partition() メソッドの処理

Partition() メソッドでは、渡された範囲の最も左側の要素をピボットとして選択します。そして、左側からはピボット以上の要素を探すポインタ（left）、右側からはピボット以下の要素を探すポインタ（right）を移動させ、条件を満たす2つの要素を見つけるたびに交換を行います。この操作を繰り返して、ピボットを配列内の正しい位置へと配置します。

int pivot;
pivot = arr[left];
while (true) {
    while (arr[left] < pivot) {
        left++;
    }
    while (arr[right] > pivot) {
        right--;
    }
    if (left < right) {
        int temp = arr[right];
        arr[right] = arr[left];
        arr[left] = temp;
    } else {
        return right;
    }
}

左右のポインタが出会った時点で、ピボットより小さい要素はすべて左側に、大きい要素はすべて右側に集まっています。このときの位置（right の値）を戻り値として返すことで、次の再帰呼び出しにおける分割点となります。

計算量について

クイックソートの平均計算量は O(n log n) であり、大規模なデータに対して高速に動作することで知られています。一方、最悪の場合（毎回極端に偏った分割が起こる場合）には O(n²) まで悪化する可能性があります。ピボットの選び方を工夫することで、最悪ケースの発生確率を下げることができます。