CODEWITHSUNDEEP
javaalgorithmdutch-national-flag-problem
tmgr
tmgr

Reputation: 1187

Dutch National Flag - Not working for larger array

My below Dutch National Flag solution doesn't seem to work for the given input array containing only 3 elements - 0, 1 and 2.

If I reduced the size of array, it works. I'm not able to identify the error.

Am I missing something ? 

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 
        }
    }
}

UPDATE : Above same code works for smaller size array : http://ideone.com/bgEgCs

Upvotes: 3

Views: 350

Answers (2)

orangegoat
orangegoat

Reputation: 2703

When you are arr[pivot] == high you should not move your pivot point the value you are switching with may not be the low value you are looking to switch with. You only know that the upper is now in the correct position

} else if (inArray[pivot] == high) {
    temp = inArray[pivot];
    inArray[pivot] = inArray[upper];
    inArray[upper] = temp;
    pivot++; //This line is not needed
    upper--;

Upvotes: 1

JB Nizet
JB Nizet

Reputation: 692081

The error is that the pivot must not be incremented when arr[pivot] == high.

And yes, I cheated: http://en.wikipedia.org/wiki/Dutch_national_flag_problem

Upvotes: 2

Related Questions