-2

Javaでいくつかの異なるタイプのクイックソートを実装しようとしていますが、どの実装も機能していないようです。私はインターネット全体を見てきましたが、私のコードは私が見つけたすべてのコードと非常によく似ているので、何が悪いのかわかりません。私のコードは次のとおりです:(これは完全ではありませんが、1つのクイックソートで問題が見つかった場合は、他のバージョンも機能することに注意してください）編集：私が抱えている問題は、配列がソートされないことです正しく。isSortedという単純なメソッドを実行して、配列が正しくソートされているかどうかを確認します。他のソート方法（挿入ソート、ヒープソートなど）でも機能しますが、クイックソートの実装で使用するとfalseが報告されます

public static void quickSort(int[] A) {
        flag=0;
        quickSortHelper(A, 0, A.length-1);
    }

public static void quickSortHelper(int [] A, int low, int high){
        if(low<high){
            if(flag==0){
            int q=DPartition(A, low,high,A[high]);
            quickSortHelper(A,low,q-1);
            quickSortHelper(A,q+1,high);
        }

public static int DPartition(int [] A, int low, int high,int pivot){
        int p=pivot;
        int i=low;
        int j=high-1;
        while (i<=j){
            while(i<=j && A[i]<=p){
                i=i+1;
            }
            while(j>=i && A[j]>=p){
                j=j-1;
            }
            if (i<j){
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            }

        }
      int temp = A[i];
      A[i] = A[p];
      A[p] = temp;
      return i;
    }
4

1 に答える 1

3

バグはあなたのDPartitionメソッドにあります。クイックソートでは、特定の方向に移動し、スワッピングが実行されるとすぐに、移動する方向を変更します。ただし、上記のコードでは、スワップせずに両方向に移動しています。

最初のinner-whileループはスワップの場所を見つけますが、スワップする代わりに、反対方向に動き始める次のinner-whileから始めました。それは誤りです。

配列に方向を格納するために、もう1つの変数を維持する必要があります。

次のようにコードを変更してみてください（テストされていません）：-

// No need to pass `pivot` as parameter. Just use `high`.
public static int DPartition(int [] A, int low, int high) {  
    int i=low;
    int j=high;
    boolean leftToRight = false;
    boolean rightToLeft = true;

    while (i <= j) {   // Iterate till middle

        if (leftToRight) {  // Move left to right

            while(i <= j && A[i] <= A[j]){
                i=i+1;  // Move right until condition is satisfied
            }
            if (i < j) {   // If `i` has not moved beyond `j`. Perform Swap
                swap(i, j, A);   // Pass index for swapping along with array.
            }
            leftToRight = false;   // Toggle to change direction.
            rightToLeft = true;

        } else if (rightToLeft) {  // Move right to left.

            while(j >= i && A[j] >= A[i]){
                j=j-1;
            }
            if (j > i) {    // If j has not moved beyond `i`. Perform Swap
                swap(i, j, A);
            }
            rightToLeft = false;   // Toggle to change the direction
            leftToRight = true;
        } 
    }
    return i;   // Return `index` to split.
}

public static void swap(int p, int q, int[] a) {
    System.out.println("p = " + p + ", q = " + q);
    int temp = a[p];
    a[p] = a[q];
    a[q] = temp;
}
于 2012-11-30T05:38:55.233 に答える