Национальный флаг Нидерландов - не работает для большего массива

Мое ниже решение голландского национального флага, похоже, не работает для данного входного массива, содержащего только 3 элемента - 0, 1 и 2.

Если я уменьшил размер массива, он работает. Я не могу определить ошибку.

Я что-то пропустил ?

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


java algorithm dutch-national-flag-problem
person tmgr    schedule 17.07.2013    source источник
comment
примечание: вы можете использовать Arrays.toString(arr) для печати ваших массивов   -  person orangegoat    schedule 17.07.2013

Ответы (2)


arrow_upward
2
arrow_downward

Ошибка заключается в том, что сводная точка не должна увеличиваться, когда arr[pivot] == high.

И да, я обманул: http://en.wikipedia.org/wiki/Dutch_national_flag_problem

person JB Nizet    schedule 17.07.2013

arrow_upward
1
arrow_downward

Когда вы 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--;
person orangegoat    schedule 17.07.2013