Interesting sorting problem

Question

There are ones, zeroes and ‘U’s in a particular order. (E.g. “1001UU0011”) The number of ones and zeroes are the same, and there’s always two ‘U’s next to each other. You can swap the pair of ‘U’s with any pair of adjacent digits. Here’s a sample move:

      __
     /  \
1100UU0011 --> 11001100UU

The task is to put all the zeroes before the ones.

Here's a sample solution:

First step:
  __
 /  \
1100UU0011

Second step:
  ____
 /    \
UU00110011

000011UU11  --> DONE

It’s pretty easy to create a brute-force algorithm. But with that it takes hundreds or even thousands of moves to solve a simple one like my example. So I’m looking for something more “clever” algorithm.

---

It's not homework; it was a task in a competition. The contest is over but I can’t find the solution for this.

Edit: The task here is the create an algorithm that can sort those 0s and 1s - not just output N 0s and N 1s and 2 Us. You have to show the steps somehow, like in my example.

Edit 2: The task didn't ask for the result with the least moves or anything like that. But personally I would love the see an algorithm that provides that :)

Answer 1

I think this should work:

• Iterate once to find the position of the U's. If they don't occupy the last two spots, move them there by swapping with the last two.
• Create a variable to track the currently sorted elements, initially set to array.length - 1, meaning anything after it is sorted.
• Iterate backwards. Every time you encounter a 1:
  • swap the the one and its element before it with the U's.
  • swap the U's back to the the currently sorted elements tracker -1, update variable
• Continue until the beginning of the array.