Javaで実装する反復クイックソート(非再帰)プログラムの解説

クイックソートは通常、再帰呼び出しによって実装されますが、再帰を使わずに明示的なスタックを利用することでも実装できます。これを「反復クイックソート(Iterative Quick Sort)」と呼びます。以下は、そのJavaによる実装例です。

サンプルコード

public class Demo{
    void swap_vals(int arr[], int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    int partition(int arr[], int l, int h){
        int x = arr[h];
        int i = (l - 1);
        for (int j = l; j <= h - 1; j++){
            if (arr[j] <= x){
                i++;
                swap_vals(arr, i, j);
            }
        }
        swap_vals(arr, i + 1, h);
        return (i + 1);
    }
    void quick_sort(int arr[], int l, int h){
        int my_list[] = new int[h - l + 1];
        int top = -1;
        my_list[++top] = l;
        my_list[++top] = h;
        while (top >= 0){
            h = my_list[top--];
            l = my_list[top--];
            int p = partition(arr, l, h);
            if (p - 1 > l){
                my_list[++top] = l;
                my_list[++top] = p - 1;
            }  
            if (p + 1 < h){
                my_list[++top] = p + 1;
                my_list[++top] = h;
            }
        }
    }
    public static void main(String args[]){
        Demo my_ob = new Demo();
        int my_arr[] = { 34, 76, 41, 32, 11, 0 , 91, 102, -11};
        my_ob.quick_sort(my_arr, 0, my_arr.length - 1);
        int i;
        System.out.println("After iteratively performing quick sort, the array is ");
        for (i = 0; i < my_arr.length; ++i)
        System.out.print(my_arr[i] + " ");
    }
}

実行結果

After iteratively performing quick sort, the array is
-11 0 11 32 34 41 76 91 102

プログラムの構成

Demo クラスには、次の3つのメソッドが定義されています。

• swap_vals:一時変数(temp)を使用して、配列内の2つの要素の値を入れ替えるメソッドです。
• partition:末尾の要素をピボットとして選び、それより小さい要素を左側へ、大きい要素を右側へ移動させることで、配列を2つの部分に分割します。戻り値としてピボットの最終的な位置(インデックス)を返します。
• quick_sort:再帰の代わりに自前のスタック(my_list 配列)を使い、処理すべき部分配列の範囲(l と h)を積み上げながら、partition を繰り返し適用して並べ替えを行います。

main メソッドの流れ

main メソッドでは、まず Demo クラスのインスタンスを生成し、ソート対象となる整数型の配列を用意します。続いて quick_sort メソッドを呼び出して配列全体をソートし、最後に結果をコンソールに出力しています。

反復版のメリット

再帰版と比較して、反復クイックソートはスタックオーバーフローのリスクを抑えられる点が大きな利点です。特にデータ量が多く再帰が深くなりやすいケースでは、明示的なスタック管理により安全に動作させることができます。平均計算量は O(n log n)、最悪時は O(n²) であり、これは再帰版と同様です。