3

まず第一に、これは宿題の質問であり、私はかなりの量の試みを行った.

Java でクイックソートを変更して、式を使用して配列内の 9 つの値の疑似中央値としてピボットを設定するように依頼されました。i * (n-1) /8

computeMedian3 つの整数を受け取り、最高値を決定してからその値を返すメソッドを作成しました。

コード：

public static int computeMedian(int x, int y, int z)
    {
        if((x >= y && x <= z) || (x >= z && x <= y)) {return x;}
        else if((y >= x && y <= z) || (y >= z && y <= x)) {return y;}
        else if((z >= x && z <= y) || (z >= y && z <= x)) {return z;}
        else { return 0; }
    }

次に、現在の値を取得し、それらを使用してピボットを構築するfindPivotメソッドでそれを使用しましたarray, from, to

そのコードは次のとおりです。

public static int findPivot(int[] a, int from, int to)
    {
        if(a.length <= 7)
        {
            return a[(to)/2];
        }
        else if(a.length > 7 && a.length <= 40)
        {
            return computeMedian(a[from], a[(to)/2] , a[to]);
        }
        else
        {
            int x = computeMedian(a[0 * (to) / 8], a[1 * (to) / 8], a[2 * (to) / 8]);
            int y = computeMedian(a[3 * (to) / 8], a[4 * (to) / 8], a[5 * (to) / 8]);
            int z = computeMedian(a[6 * (to) / 8], a[7 * (to) / 8], a[8 * (to) / 8]);
            return computeMedian(x,y,z);
        }
    }

このメソッドは、サイズが 40 以下の配列の並べ替えには問題なく機能しますが、サイズが 40 を超えるとすぐにスタック オーバーフロー エラーが発生し、その部分のcomputeMedianメソッドに戻ります。else {}そこに置くと> 40の部分で機能することに注意してください。ただしreturn computeMedian(a[from], a[(to)/2] , a[to]);、3セットの中央値の中央値ではなく、3つの値の中央値にすぎません。

現在、これは私がfindPivotクイックソートパーティショニングメソッドにプラグインした方法です:

private static int modPartition(int[] a, int from, int to)
    {
        int pivot = findPivot(a, from, to);
        int i = from - 1;
        int j = to + 1;
        while(i < j)
        {
            i++; while (a[i] < pivot) { i++; }
            j--; while (a[j] > pivot) { j--; }
            if (i < j) { swap(a, i, j); }
        }
        return j;
    }

computeMedian私の方法がより大きなデータセットで機能しない理由について、私はかなり困惑しています。i * (n-1) / 8forループを介して値を配列に配置し、それらをソートして途中で値を返すこと、および値を配列に配置pして呼び出すことを試みましたcomputeMedian(computeMedian(p[0], p[1], p[2]), computeMedian(p[3],p[4],p[5]),...etcが、同じスタックオーバーフローの問題が発生しますが、移動する傾向があります私のコードのさまざまな部分と私を輪に導きます。

必要に応じてスニペットを投稿できますが、私の問題はおそらくここにあると思います。

助けてくれてありがとう。私はまだ学んでいますが、これを理解することは、将来的に自分で問題を解決するのに完全に役立つと思います.

スタック トレースの問題行は次のとおりです。 行 16:int p = modPartition(a, from, to); 行 18modSort(a, p+1, to); 行 23int pivot = findPivot(a, from, to);

私のmodSortメソッド全体もここにあります：

public static void modSort(int[]a, int from, int to)
    {
        if(from >= to) { return; }
        int p = modPartition(a, from, to);
        modSort(a, from, p);
        modSort(a, p+1, to);
    }
4

2 に答える 2

0

スタック オーバーフローの問題のコードとエラー メッセージを実際に含めたので、私たちはあなたを助けることができます。

スタック トレースから、18 行目が繰り返されているため、無限再帰がの 2 回目の呼び出しである可能性が高いことがわかります。modSort

その呼び出しと着信パラメーターの唯一の違いは 2 番目のパラメーターであるため、p未満であることに賭けますfrom。

それを確認する最善の方法は、古き良きprintステートメントを挿入することです。

public static void modSort(int[]a, int from, int to)
{
    if(from >= to) { return; }
    int p = modPartition(a, from, to);
    System.out.println("from=" + from + ", to=" + to + ", p=" + p);
    modSort(a, from, p);
    modSort(a, p+1, to);
}

結果の出力には、何が問題なのかという非常に明確なパターンが示されるはずです。

于 2015-09-07T00:21:40.253 に答える