What's wrong with my Dutch National Flag algorithm?

I'm trying to turn an array like this:

0, 1, 2, 2, 1, 0, 1, 0, 0, 1, 2

into this:

0 0 0 0 1 1 1 1 2 2 2

Here is my code:

public static int[] sortDNF(int[] tape) {
    int smaller = 0; // everything with index < smaller is 0
    int bigger = tape.length - 1; // everything with index > bigger is 2
    int current = 0; // where we are looking now
    int tmp;

    while (current <= bigger) {
        if (tape[current] == 0) {
            tmp = tape[smaller];
            tape[smaller] = tape[current];
            tape[current] = tmp;
            smaller++;
        }
        if (tape[current] == 2) {
            tmp = tape[bigger];
            tape[bigger] = tape[current];
            tape[current] = tmp;
            bigger--;
开发者_如何学Python        }
        current++;
    }

    return tape;
}

This is what it produces:

 0  0  0  1  1  1  1  0  2  2  2 

What is my problem?

A guess:

You should not be increasing current every time through the loop since that is supposed to represent the partition between the 1's and the unknowns. For example, when you hit the first 2 you end up swapping it with another 2 and then moving on. The fact that the 2 later gets swapped for a 0 is accidental. The elements between smaller and current should always be 1's and that is broken.

current++ should only be done in the tape[current] != 2 case. It's ok to do it when tape[current] = 0 because you haven't changed the [smaller -> current] = 1-only condition. And it's ok to move it when tape[current] = 1 because that satisfies the 1-only condition.

...but I haven't tried it.

For those who haven't studied the problem, sorting is sufficient to provide a solution, but it is (or can be) more than necessary. Solving the DNF problem only requires that all like items be moved together, but you don't have to place unequal items in any particular order.

It's pretty easy to solve DNF with expected O(N) complexity, where (most normal forms of) sorting have O(N lg N) complexity. Instead of rearranging the input elements, it's much easier to simply count the elements with any given value, then print out the right number of each. Since the order of unequal elements doesn't matter, you normally store your counts in a hash table.

The problem is that you reply on (possible nonexistent) values later in the chain to swap incorrectly skipped 1 values, try your algo on the trivial case of:

1 2 0

the 2 gets swapped in the right spot, but the current index has been advanced over the index 0 ends up in resulting in:

1 0 2

So don't increment current before you inspect the new value at that index.

You need to increment current only during the check for 1 and check for 2. When you are checking for 3 you just need to decrement bigger. Here the working solution. BTW this works for the array of values between 1-3. You can change it to 0-2 if you so wish.

The program produces the following output given a random number array as follows:

Original Array : [1, 3, 3, 3, 2, 2, 2, 1, 2, 2, 1, 3, 3, 2, 1, 1, 3]

Sorted Array : [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3]

private static int[] sortUsingDutchNationalFlagProblem(int[] array) 
{
    System.out.println("Original Array : " + Arrays.toString(array));
    int smaller = 0;    // everything with index < smaller is 1
    int bigger  = array.length - 1; // everything with index > bigger is 3
    int current = 0;        // where we are looking now
    int tmp;
    while (current <= bigger) {
            if (array[current] == 1) {
                    tmp            = array[smaller];
                    array[smaller] = array[current];
                    array[current] = tmp;
                    smaller++;current++;
            }
            if(array[current] == 2)
                current++;
            if (array[current] == 3) {
                    tmp            = array[bigger];
                    array[bigger]  = array[current];
                    array[current] = tmp;
                    bigger--;
            }
    }
    System.out.println("Sorted Array   : " + Arrays.toString(array));
    return array;
}

Here is my approach using Java

public static void dutchNationalFlagProblem(int[] input) {
    int low=0, mid=0, high = input.length -1;
    while(mid <=high) {
        switch (input[mid]) {
            case 0:
                swap(input, low++, mid++);  
                break;
            case 1:
                mid++;  
                break;
            default :
                swap(input, mid, high--);
                break;
        }
    }       
}

private static void swap(int[] input, int firstIndex, int secondIndex) {
    int temp = input[firstIndex];
    input[firstIndex] = input[secondIndex];
    input[secondIndex] = temp;

}

Here is the corresponding test cases

@Test
public void dutchNationalFlagProblemTest() {
    int[] input = new int[]{0,1,0,2,2,1};
    ArrayUtils.dutchNationalFlagProblem(input);
    assertThat(input, equalTo(new int[]{0,0,1,1,2,2}));
}

I'm going to propose an easier solution :-)

public static int[] sortDNF(int[] tape) {
  Arrays.sort(tape);
  return tape;
}

As far as what's wrong with your solution, when the current element is 2 and it's swapped with the element near the end of the list, the element it's swapped with may not be 2, but you're incrementing current and not looking at this position again.

public static int[] sortDNF(int[] tape) {
    int smaller = 0; // everything with index < smaller is 0
    int bigger = tape.length - 1; // everything with index > bigger is 2
    int current = 0; // where we are looking now
    int tmp;

    while (current <= bigger) {
            if (tape[current] == 0) {
                    tmp = tape[smaller];
                    tape[smaller] = tape[current];
                    tape[current] = tmp;
                    smaller++;
            }
            else if (tape[current] == 2) {
                    tmp = tape[bigger];
                    tape[bigger] = tape[current];
                    tape[current] = tmp;
                    bigger--;
            }
            current++;
    }

    return tape;
}

Below program is giving right result, do you guys see any issue in this simple innocent programming approach?

public class Test {
    public static void main(String[] args) {
        int arr[] = {1, 2, 0, 2, 1, 1, 1, 0, 0, 2, 2, 1, 0, 1, 2, 0, 2};
        int x0 = 0, x1 = 0, x2 = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0)
                x0++;
            if (arr[i] == 1)
                x1++;
            if (arr[i] == 2)
                x2++;
        }
        int i = 0;
        for (int j = i; j < x0; j++)
            arr[i++] = 0;
        for (int j = i; j < x0+x1; j++)
            arr[i++] = 1;
        for (int j = i; j < x0+x1+x2; j++)
            arr[i++] = 2;

        printArray(arr);

    }

    private static void printArray(int[] arr) {
        for (int a : arr) {
            System.out.print(a + " ");
        }
    }
}