sorting an array of three kinds of stones

) ) [This puzzle is better suited to comp.programming and/or ) rec.puzzles; xposted and followups set accordingly.] ) ) On Thu, 28 Oct 2004, meital wrote: )> )> There are three kinds of stones: red,green and blue. )> Each cell of the array contains one stone. )> The array needs to be sorted so that all the red )> stones will come first, then the blue ones and )> then all the green ones. )> There are N stones, as the number of cells in the array. )> )> switch(i,j)- switch the stone in the i-th place with the )> one in the j-th place. )> color(i)- reveals the color of the stone in the i-th place. )> )> These functions can be used only N times. ) ) You mean, you can call 'color' N times, and then call 'switch' ) N times? Then the problem is trivial (though a complete working ) solution may require some thought). ) If you mean that you can only make N function calls in total, ) to both 'color' and 'switch' combined, then I think there is no ) solution possible.

Obviously, because you could never be sure you have the right solution unless you have called color() on each and every stone.

) Bonus puzzle: What is the minimum number of bits of temporary ) storage you need for a solution, if you can call each function ) N times?

3*ceil(log2(N)) bits, I think. That would be for the standard Dutch Flag Algorithm.

) How many calls to 'switch' do you need, in the minimum case?

None, obviously. The minimum case is that all stones are red. If you want to minimise the worst-case number of switches, it gets more difficult.

) What is the minimum big-Oh expecting running time of the fastest ) solution?

You need to examine all the items, that makes it O(N).

If you want the big-Oh expected number of switches, then it's more difficult.

SaSW, Willem

'Arthur J. O'Dwyer' schrieb:

??? Please explain.

2/3 n switches is the worst case.

You get that if you have stones in equal number for all colors, and then rotate the color scheme.

target: rgb rrrgggbbb actual: gbr gggbbbrrr

To undo a single gbr rotation, you need 2 switches; which means your efficiency is 2 siwtches per 3 elements, or 2/3.

All other permutations are easier, because a simple pair swap that leaves both stones in the right section has an efficiency of 1/2; and once you have done all of those that you could, you're left with only triple rotations as above.

Exercise: Prove that the remaining triple rotations are all in one 'direction'!

Cheers

) 'Arthur J. O'Dwyer' schrieb: )> Yeah. *slaps forehead* I was thinking along those lines, but I hadn't )> gotten my thoughts clearly organized before posting. (Interestingly, )> if you only have two different colors of stones, you don't need to )> inspect every stone. ) ) ??? ) Please explain.

In RRRXBBB you don't care if the single X is R or B, so you can get away with N-1 calls to colour().

It could also be G, so this is also the pathological case where you could get away with N-1 colour() calls when there are 3 colours: Assuming you inspected N-1 stones, and they all turned out to be either red or blue, then you can put the remaining stone in the middle, and they would be sorted in any of the three cases.

SaSW, Willem

Willem schrieb:

Ah, ok. So you don't need to inspect every stone, but you do need to inspect every stone but one. I can see the savings.

Cheers

Make that 'programmers' deadlines are way too tight for them to have time to search for better ones'.

^^^^^

'Underpaid'?

It doesn't surprise me that there is an algorithm more efficient than the most efficient one that Dijkstra would consider to be

Perhaps in the days before google.

Or lacking a budget entirely. If my choice is to implement the best algorithm I know of, or pay $100 out of my own pocket for a better one, I keep the $100 and the company deals with suboptimal performance.

What does surprise me is that no one seems to use it; there's no mention of it on the google-reachable net, even on the pages of people who are fanatic about speeding up sorts.

Matthew Russotto schrieb:

I think except as a demonstration piece for algorithm proof it is of no big use; I've seen it mentioned as being in use as part of quicksort when using a 'fat pivot', but usually the pivot is quite small. Knuth makes it the object of an exercise.

I have today implemented a Dutch National Flag Algorithm that takes N+2 calls to color() and an expected 0.38N or so calls to switch() on a uniform flag distribution, with worst case at 2/3N. This is better than the Bentley and McIlroy algorithm mentioned in Knuth, but were I to use it for quicksort, with the pivot much smaller than the rest of the data, I'd be less efficient than their algorithm (I think) because then I'd be moving the pivot around more.

Oh, and it's all nicely structured, of course.

The point is that this seems to be a sort that is of little practical use if you do 'real' sorting.

Hmm, reading http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/ ,there's a 3-way quicksort suggested. Doing two 3-way runs at .375N = .75 N to get 9 partitions is about as good as doing 3 2-way runs at 0.25N=.75 N switches. It probably comes down to looking at the overhead?

Does anyone know uses of the Dutch Flag in practice?

Cheers