What's wrong with my Dutch National Flag algorithm?

Question

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--;
  }
  current++;
 }

 return tape;
}

This is what it produces:

 0  0  0  1  1  1  1  0  2  2  2

What is my problem?

Answer 1

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.

Answer 2

How about Quicksort.

Answer 3

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.

Answer 4

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.

Answer 5

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.