19
$\begingroup$

How can I sort a list of 5 integers such that in the worst case it takes 7 compares? I don't care about how many other operations are performed. I don't know anything particular about the integers.

I've tried a few different divide and conquer approaches which get me down to 8 compares, such as following a mergesort approach, or combining mergesort with using binary search to find the insertion position, but every time I end up with 8 compares worst case.

Right now I'm just looking for a hint, not a solution.

$\endgroup$
  • $\begingroup$ Have you tried writing the "compare-to" tree? It has $5! = 120$ leaves, each corresponding to a permutation of the integers. If you don't know what I mean by the "compare-to" tree, do you know the proof that you need $n \log n$ comparisons? Ps, what makes you think it's possible? $\endgroup$ – Pål GD Apr 1 '13 at 18:52
  • 1
    $\begingroup$ Well, in 8 bit two's complement, if(x > y) is the same as if((x - y) & 0x80) which is hardly a compare. I guess we should forget that the objects are integers and assume we must use some magical compare(x, y) function to compare those objects... $\endgroup$ – Karolis Juodelė Apr 1 '13 at 20:21
  • 2
    $\begingroup$ Does 'check out section 5.3 on optimal sorting in Volume 3 of The Art Of Computer Programming, which covers precisely this question' count as a hint or a solution? :-) $\endgroup$ – Steven Stadnicki Apr 1 '13 at 22:20
  • 3
    $\begingroup$ The bound is really that $2^c \ge n!$, and $5! = 120 < 2^7 = 128$. So it is possible (in principle). $\endgroup$ – vonbrand Apr 2 '13 at 0:07
  • 1
    $\begingroup$ related: Sorting an array with minimal number of comparisons $\endgroup$ – Janus Troelsen May 12 '13 at 19:11
23
$\begingroup$

There is only one way to start this process (and for nearly all of your decisions of what to compare in later steps, there is only one correct one). Here's how to figure it out. First, note that there are $2^7 =128$ possible answers you can get for your comparisons, and $5! = 120$ different permutations you need to distinguish between.

The first comparison is easy: you have to compare two keys, and since you don't know anything about them, all choices are equally good. So let's say you compare $a$ and $b$, and find that $a \leq b$. You now have $2^6 = 64$ possible answers left, and $60$ possible permutations remaining (since we have eliminated half of them).

Next, we can either compare $c$ and $d$, or we can compare $c$ to one of the keys we used in the first comparison. If we compare $c$ and $d$, and learn that $c \leq d$, then we have $32$ remaining answers and $30$ possible permutations. On the other hand, if we compare $c$ with $a$, and we discover that $a \leq c$, we have $40$ possible permutations remaining, because we have eliminated $1/3$ of the possible permutations (those with $c \leq a \leq b$). We only have $32$ possible remaining answers, so we're out of luck.

So now we know that we have to compare the first and second keys, and the third and fourth keys. We can assume that we have $a\leq b$ and $c \leq d$. If we compare $e$ to any of these four keys, by the same argument we used in the previous step, we might only eliminate $1/3$ of the permutations remaining, and we're out of luck. So we have to compare two of the keys $a,b,c,d$. Taking into account symmetry, we have two choices, compare $a$ and $c$ or compare $a$ and $d$. A similar counting argument shows we must compare $a$ and $c$. We can assume without loss of generality that $a \leq c$, and now we have $a \leq b$ and $a \leq c \leq d$.

Since you asked for a hint, I won't go through the rest of the argument. You have four comparisons left. Use them wisely.

$\endgroup$
  • $\begingroup$ How did you get that comparing $a$ to $c$ only gets you down to 40 permutations? $\endgroup$ – Robert S. Barnes Jun 4 '13 at 6:05
  • 1
    $\begingroup$ @Robert: Suppose you have $a \leq b$ and $a \leq c$. Then there are two permutations of $a,b,c$ consistent with these constraints, $a < b < c$ and $a < c < b$. For each of these two permutations, there are four places you can add $d$ and five places you can add $e$. $\endgroup$ – Peter Shor Jun 4 '13 at 10:59
8
$\begingroup$

You can find this in The Art of Computer Programming vol III, by D.Knuth, but the strategy is as this (I'll assume you have array $\{a,b,c,d,e\}$): If you want hint read just first two lines of my answer

  • First group pairs of numbers: $(a,b), (c,d)$.
  • Compare pairs to sort them e.g: $a<b, c<d$.
  • Compare smallest elements of pairs, we get result e.g $a<c$.
  • Compare the last element $e$, with bigger element in last comparison ($c$)
    • If $e<c$, is easy to end up with 3 remaining comparison. Finished.
    • If $e>c$ then you should sort $\{b,c,d,e\}$ with knowledge $c<e, c<d$.
      • $Compare(d,e)$, if $d < e$ then
        • $Compare(b,d)$, if $b>d$
          • $Compare(b,e)$. Finished.
        • if $b<d$
          • $Compare(b,c)$. Finished.
      • if $d > e$
        • $Compare(b,e)$ if $b>e$
          • $Compare(b,d)$. Finished.
        • if $b<e$
          • $Compare(b,c)$. Finished.

All above mentioned ways are cause to at most three comparison after first comparison of $e$ with $c$. (means 7 at most).

$\endgroup$
  • $\begingroup$ Are you sure this is correct? Assume you get the following results: a < b, c < d, a < c and then c < e, b < e, c < b and d < e. The orderings a < c < b < d < e and a < c < d < b < e are both consistent with them. The reason is that b and d are never compared, implicitly or explicitly. Maybe I'm mistaken somewhere, if so please correct me. $\endgroup$ – George Apr 3 '13 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.