4

100000 の入力サイズで実行するクイックソート プログラムを作成しています。500 のサイズで実行しようとしましたが、正常に動作しますが、100 万の入力があると、プログラムは次のエラー コードで中断します。

「java.lang.StackOverflowError」

この問題を解決する方法を教えてください。無限再帰に陥っていないことは確かです。再帰メソッドを返す基本的なケースがあります。

public class count_comparisons {

    public static int count_comp =0;
    public static int partitioning(int[] A, int lo, int hi) {

        int pivot = A[lo];

        int i=lo+1;
        int j=lo+1;
        int k=lo;

        for ( j=lo+1;j<=hi;j++) {            
            if (A[j] < pivot) {
                swap(A,i,j);
                i++;
            }
        }
        swap(A,i-1,lo);        
        return i-1;
    }

    public static int quicksort(int[] A, int lo, int hi) {
        if (lo>=hi) return 0;
        int pivot = partitioning(A,lo,hi);

        //StdOut.println("Pivot index is "+ pivot +" and entry at pivot is " + A[pivot]);

        StdOut.println("Lo is "+ lo +" and Hi is " + hi);
        int h = quicksort(A,lo,pivot-1);
        int m = quicksort(A,pivot+1,hi);
        //StdOut.println("First half count is "+h);
        //StdOut.println("Second half count is "+m);
        count_comp = count_comp + h + m;
        return (hi-lo);
    }

    public static void quicksort(int[] A,int N) {  
        int k = quicksort(A,0,N-1);
        count_comp = count_comp + k;
        //StdOut.println(" First count is "+k);
    }

    private static void swap(int[] A, int j,int k) {
        int temp = A[j];
        A[j] = A[k];
        A[k] = temp;
    }

    public static void main(String[] args) {
        In in = new In("input_file.txt"); 
        int N=569;
        int[] A = new int[569];
        int i=0;
        while (!in.isEmpty()) {
            A[i++] = in.readInt();
        }
        count_comparisons.quicksort(A,N);

        for( int h=0;h<N;h++) {}
            //StdOut.print(A[h]);
        StdOut.println();
        StdOut.println(count_comparisons.count_comp);

    }
}
4

2 に答える 2

2

再帰は、スタック オーバーフローを引き起こすために無限である必要はありません。必要なのは、スタックをオーバーフローするのに十分な長さだけです。

クイックソートは非常に遅い場合があります。特に不幸な状況でn-1は、最悪の場合のO(n^2).

明示的なスタック データ構造を使用して再帰を行わずにコードを書き直すか、JVM がプログラムのスレッドに割り当てるスタックのサイズを大きくするという 2 つの選択肢があります。

于 2013-07-08T15:00:51.703 に答える
0

末尾再帰の除去と、再帰の深さを制限する小さいサブセットへの再帰のみを使用するトリックがあります。

于 2013-07-08T15:03:40.127 に答える