0

これがコードです。出力はほぼ正しくソートされた配列ですが、いくつかの要素が順不同です。誰でもエラーを見つけることができますか?

スワップとクイックソートの方法は正しいと確信していますが、念のためここにすべての方法を掲載しています。

package quicksort;
import java.util.Random;
import java.util.Arrays;

public class QuickSort {

/**
 * @param args the command line arguments
 */

private static int[] u;

public static void main(String[] args) {

    u = makeArray(100);
    System.out.println(Arrays.toString(u));

    quicksort(0, u.length - 1);
    System.out.println(Arrays.toString(u));

}

public static int[] makeArray(int n) {

    int[] a = new int[n];
    int j;
    Random r = new Random();

    for (int i = 0; i < n; i++) {
        j = (r.nextInt(100) + 1);
        a[i] = j;
    }

    return a;
}

public static int partition(int left, int right, int pivot) {

    int p = pivot;    // pivot
    int lPt = left - 1;
    int rPt = right + 1;

    while (true) {

        while ((lPt < right) && (u[++lPt] < p));

        while ((rPt > left) && (u[--rPt] > p));

        if (lPt >= rPt) {
            break;
        } else {

            swap(lPt, rPt);
            System.out.println("Swapping " + lPt + " " + rPt);

        }


    }

    return lPt;
}

public static void swap (int a, int b) {        
    int temp = u[a];
    u[a] = u[b];
    u[b] = temp;
}

public static void quicksort(int l, int r) {

    if (r - l <= 0) {
        return;

    } else {

        int part = partition(l, r, u[l]);

        quicksort (l, part - 1);
        quicksort (part + 1, r);

    }
}

}

4

2 に答える 2

2

問題は分割方法にあります。スワップの最後に、ピボット要素が正しい位置に配置されていません。ピボットの値ではなく、ピボット要素の位置を渡すようにメソッド シグネチャを変更したので、quicksort() で次のように記述します。

int part = partition(l, r, l);

ピボット メソッドの本体で、ピボット要素をセクションの最後にスワップしました (右にスワップ)。スワップでこの要素を無視するために、rPT の初期化で「+ 1」を削除しました。次に、while ループの後にステートメントを追加して、ピボット要素を所定の位置に移動しました。これら 3 つの変更により、メソッドは次のようになります。

public static int partition(int left, int right, int pivotPosition) {

    int p = u[pivotPosition];    // pivot

    // Move pivot to the end
    swap(pivotPosition, right);

    int lPt = left - 1;
    int rPt = right;

    while (true) {

        while ((lPt < right) && (u[++lPt] < p));

        while ((rPt > left) && (u[--rPt] > p));

        if (lPt >= rPt) {
            break;
        } else {

            swap(lPt, rPt);
            System.out.println("Swapping " + lPt + " " + rPt);
        }

    }

    // Put pivot in its place
    swap(lPt, right);

    return lPt;
}

これらの変更により、コードは機能します。

于 2013-05-03T05:21:02.400 に答える
0

左側のリストでピボット要素よりも大きい値を見つけ、右側のリストでピボット要素よりも小さい値を見つけてから、値を交換する必要があります。

package quicksort;
import java.util.Random;
import java.util.Arrays;

public class QuickSort {
    /**
     * @param args the command line arguments
     */
    private static int[] u;

    public static void main(String[] args) {

        u = makeArray(10);
        System.out.println(Arrays.toString(u));

        quicksort(0, u.length - 1);
        System.out.println(Arrays.toString(u));

    }

    public static int[] makeArray(int n) {
        int[] a = new int[n];
        int j;
        Random r = new Random();
        for (int i = 0; i < n; i++) {
            j = (r.nextInt(100) + 1);
            a[i] = j;
        }
        return a;
    }

    private static void quicksort(int low, int high) {
        int i = low, j = high;
        int pivot = u[low];
        while (i <= j) {
            while (u[i] < pivot) {
                i++;
            }
            while (u[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchange(i, j);
                i++;
                j--;
            }
        }
        if (low < j) {
            quicksort(low, j); // note here
        }
        if (i < high) {
            quicksort(i, high); // note here
        }
    }

    private static void exchange(int i, int j) {
        int temp = u[i];
        u[i] = u[j];
        u[j] = temp;
    }
}
于 2013-05-03T04:47:21.220 に答える