luke.magill
BAN USERIt works but there is an O(n) solution.
- luke.magill January 12, 2012The algorithm is confusing, but it's the only constant time algorithm that can accomplish it. Don't believe me? It's a fully functioning python program, try executing it on your machine.
It has two for loops, but two for loops only means n^2 if both loops execute n times. The first loop executes n/4 (which is proportional to n) but the second loop will only ever hit the elements that the first loop didn't hit. In the end, every element will be touched by this combination of loops exactly once, making this the optimal solution.
The algorithm works as follows: Imagine you want to place one of the elements, say, element number 1 (note I'm using 0 indexing) into the right place. To do this, you will have to place it in some spot, in this case, spot 2. However, then you will have whatever was at spot 2. The idea is to place what's in spot 1 in the right place, displacing the element in 2. Then put what was in 2 in the right place, displacing another element. Eventually, you will get back to spot 1 putting the correct element in that location.
Now at this point, you will have made some number of swaps using only constant space, and all of the elements you visited will be in the right location.
The only problem is that when you start at 1, you will get back to slot 1 before you hit every element. That's what the outer loop is for.
Seriously guys, this is absolutely the best algorithm. If you don't believe me, try it.
I discovered that keeping a counter of how many items you have swapped so far should work, and won't require you to do anything. The thing is, if you have at least one element left to swap then you need to start swapping at the next available odd index.
- luke.magill January 13, 2012