0

クイックソートを実装しようとしていますが、正しい結果が得られません。これが私のコードです：

public static void quickSort(Comparable[] a, int start, int stop) {
    if (start < stop) {
        int pivot = partition(a, start ,stop);
        System.out.print("Pivot: "+a[pivot]+" Array: ");
        printArray(a);
        quickSort(a,start,pivot-1);
        quickSort(a,pivot+1, stop);
    }       
}

public static int partition(Comparable[] a, int start, int stop) {
    Comparable pivot = a[stop];
    int i = start;
    int j = stop-1;


     while (i < j) {
            while( (isLess(a[i], pivot)|| isEqual(a[i], pivot)))
                i++;
            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))
                j--;
            if(i < j)
                swap(a, i,j);
        } 

    swap(a,i, stop);

    return i;

}

入力の場合: {51,17,82,10,97,6,23,45,6,73}、結果を取得しています: 6 6 10 17 23 45 51 73 97 82 入力の場合: {12,9,4, 99,120,1,3,10}、範囲外のインデックス エラーが発生しています。私が間違っている場所で助けていただければ幸いです。

4

3 に答える 3

1

あなたの2つの問題は無関係です。

問題{51,17,82,10,97,6,23,45,6,73}は — いつ何が起こるstop == start + 1か? その後i == start == stop - 1 == j、ループに入らないwhileので、無条件にswap(a, i, stop)—a[i]が既に未満だったとしてもa[stop]。

問題{12,9,4,99,120,1,3,10}は、スタックトレースを読み取っていないようです。;-) 適切な Java コンパイラと JVM があると仮定すると、正確な行番号と問題のあるインデックスが表示されるはずなので、問題は次の行にあることがわかります。

            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

一度jに到達し-1ます。(これはpivot、 が対象範囲内の最小値である場合に発生します。) そのためのチェックを追加するだけです。

            while(j > start && (isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

(さらに言えば、対応する の場合i:

            while(i < stop && (isLess(a[i], pivot)|| isEqual(a[i], pivot)))

)

. . . コードをデバッグする方法を学ぶ必要があります。:-)

于 2012-10-26T18:18:38.727 に答える
0

Algorithms: Design and Analysis、スタンフォード大学の非常に優れたインターネット コースをお勧めします。このコースを修了すると、そのようなコードをより簡単に記述できるようになります。これは少し強化されたバージョンで、ピボットは中央値 3 として選択されています。printArray()独自の関数を記述する必要がないことに注意してください。Javaでは、でそれを行うことができますSystem.out.println(Arrays.toString(numbers)). quickSort()また、メソッドのオーバーロードを使用して、引数を 1 つだけ指定して、より洗練された方法で呼び出す方法を観察することもできます。

public class QuickSort
{

public static void main(String[] args)
{
    int numbers[] =
    { 51, 17, 82, 10, 97, 6, 23, 45, 6, 73 };
    quickSort(numbers);
    System.out.println(Arrays.toString(numbers));
}

public static void quickSort(int[] array)
{
    quickSort(array, 0, array.length - 1);
}

private static void quickSort(int[] array, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int pivot = choosePivot(array, left, right);
    pivot = partition(array, pivot, left, right);
    quickSort(array, left, pivot - 1);
    quickSort(array, pivot + 1, right);
}

private static int partition(int[] array, int pivot, int left, int right)
{
    swap(array, pivot, left);
    pivot = left;
    int i = left + 1;
    for (int j = left + 1; j <= right; j++)
    {
        if (array[j] < array[pivot])
        {
            swap(array, j, i);
            i++;
        }
    }
    swap(array, pivot, i - 1);
    return i - 1;
}

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

private static int choosePivot(int[] array, int left, int right)
{
    return medianOfThree(array, left, (left + right) / 2, right);
    // return right;
}

private static int medianOfThree(int[] array, int aIndex, int bIndex, int cIndex)
{
    int a = array[aIndex];
    int b = array[bIndex];
    int c = array[cIndex];
    int largeIndex, smallIndex;
    if (a > b)
    {
        largeIndex = aIndex;
        smallIndex = bIndex;
    }
    else
    {
        largeIndex = bIndex;
        smallIndex = aIndex;
    }
    if (c > array[largeIndex])
    {
        return largeIndex;
    }
    else
    {
        if (c < array[smallIndex])
        {
            return smallIndex;
        }
        else
        {
            return cIndex;
        }
    }
}

}
于 2012-10-26T18:18:48.040 に答える