0

I have 32 rabbits all with different weight, and I want to sort them by weight. I can use a weight which weigh 2 rabbits per time and tells me which rabbit is lighter. What's the least number of comparisons I need to sort all rabbits, and with which algorithm?

For example,if I use quicksort, I need to do 32*32(n^2 for worst case) comparisons which is probably not the algorithm with least comparison for this question.

Arch1tect
  • 4,128
  • 10
  • 48
  • 69

1 Answers1

0

I may not remember correctly how quicksort works, but here is what I would do:

Take pairs of values, and sort them in order (1-2, 3-4, etc). This creates 16 "short sorted queues". Now compare, for neighboring queues, the top elements; then the "one from the top" with the remaining top; keep working your way down the list. This takes at most 3 comparisons. Repeat for the other pairs; total so far = 8 + 4*3 = 20

By the same token, we now have 4 sets of 4 sorted rabbits, which we sort in at most 7 steps each into two sets of eight, for another 14; then 2 sets of eight, which we sort in 15. Total number: 8+12+14+15 = 49.

Showing for just four (same principle):

Assume we have rabbits ABCD, in descending weight order (we don't know that... We want them in ascending order). Algorithm:

Compare A and B - now BA

Compare C and D - now DC

Compare BD - D is lightest, goes to front of the line

Compare BC - C is lighter, next in line

Now put B ( already know it is lighter than A) and finally A

As you can see there were a total of 4 comparisons...

Floris
  • 45,857
  • 6
  • 70
  • 122
  • See my edit. I think my method may not be "pure QS"? It helps that you have a power of two for N. As described, algorithm takes `sum(i=1:n, 2^(n-i) * (2^i-1))` where `n=log2(N)` – Floris Mar 01 '13 at 05:37