3

以下のオランダ国旗ソリューションは、0、1、および 2 の 3 つの要素のみを含む特定の入力配列では機能しないようです。

配列のサイズを小さくすると、うまくいきます。エラーを特定できません。

何か不足していますか？

class DNF{

    public static void sort(int [] arr, int size, int low, int high) {

        if(size == 0)
            return;

        int lower = 0;
        int upper = size - 1;

        while(lower < size && arr[lower] == low)
            lower++;

        while(upper >=0 && arr[upper] == high)
            upper--;

        int temp = 0;
        int pivot;
        for(pivot = lower; pivot <= upper; ) {
            if(arr[pivot] == low) {
                temp = arr[pivot];
                arr[pivot] = arr[lower];
                arr[lower] = temp;
                pivot++;
                lower++;
            } else if(arr[pivot] == high) {
                temp = arr[pivot];
                arr[pivot] = arr[upper];
                arr[upper] = temp;
                pivot++;
                upper--;
            } else {
                pivot++;
            }
        }
    }
    public static void main(String [] args) {

        int arr [] = {0,1,2,1,2,0,1,1,1,0,0,0,1,0,2,1};

        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i]+" "); //0 1 2 1 2 0 1 1 1 0 0 0 1 0 2 1 
        }

        sort(arr, arr.length, 0, 2);
        System.out.println();

        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i]+" "); // 0 0 0 0 0 0 1 1 1 1 1 2 1 1 2 2 
        }
    }
}

更新: 上記の同じコードは、より小さいサイズの配列で機能します: http://ideone.com/bgEgCs

4

2 に答える 2

2

エラーは、 のときにピボットをインクリメントしてはならないということarr[pivot] == highです。

はい、私は騙されました: http://en.wikipedia.org/wiki/Dutch_national_flag_problem

于 2013-07-17T18:08:26.763 に答える
1

arr[pivot] == high の場合は、ピボット ポイントを動かしてはいけません。切り替える値は、切り替えようとしている低い値ではない可能性があります。アッパーが正しい位置にあることだけがわかります

} else if (inArray[pivot] == high) {
    temp = inArray[pivot];
    inArray[pivot] = inArray[upper];
    inArray[upper] = temp;
    pivot++; //This line is not needed
    upper--;
于 2013-07-17T18:10:08.633 に答える