20
$\begingroup$

Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons.

Solution: There are 5! = 120 possible outcomes. Therefore a binary tree for the sorting procedure will have at least 7 levels. Indeed, $2^h$ ≥ 120 implies $h $ ≥ 7. But 7 comparisons is not enough. The least number of comparisons needed to sort (order) five elements is 8.

Here is my actual question: I did find an algorithm that does it in 8 comparison but how can I prove that it can't be done in 7 comparisons?

$\endgroup$
26
$\begingroup$

The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance.

The answer is a method tailored to $n=5$, not a general algorithm. It's also not very nice. This is the outline:

  1. Sort the first two pairs.

  2. Order the pairs w.r.t. their respective larger element.

    Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$.

  3. Insert $e$ into $[a,b,d]$.

  4. Insert $c$ into the result of step 3.

The first step clearly takes two comparisons, the second only one. The last two steps take two comparisons each; we insert into a three-element list in both cases (for step 4., note that we know from $c<d$ that $c$ is smaller than the last element of the list at hand) and compare with the middle element first. That makes a total of seven comparisons.

Since I don't see how to write "nice" pseudocode of this, see here for a tested (and hopefully readable) implementation.


  1. Ph.D. thesis (Stanford University) by H.B. Demuth (1956)

    See also Electronic Data Sorting by H.B. Demuth (1985)

  2. Sorting and Searching by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
$\endgroup$
  • 5
    $\begingroup$ The test gives five points for showing it is impossible. Wonder how many points you would get for your answer :-) (Probably zero since the test can't be wrong). $\endgroup$ – gnasher729 Nov 11 '16 at 10:39
0
$\begingroup$

The theoretical lower bound on comparison based sorting is $\log(n!)$. That is to say that to sort $n$ items using only $<$ or $>$ comparisons it takes at least the base 2 logarithm of $n!$, hence $\log(5!) \approx 6.91$ operations.

Since $5!= 120$ and $2^7= 128$, using a binary decision tree you can sort 5 items in 7 comparisons. The tree figures out exactly which of the 120 permutations you have, then does the swaps needed to sort it.

It's not pretty or short code, and you should probably use code generation methods to create the decision tree and swaps rather than coding it by hand, but it works; and provably works for any possible permutation of 5 items, thus proving you can sort 5 items in no more than 7 comparisons.

$\endgroup$
  • $\begingroup$ As far as I can remember, the theoretical lower bound gives an asymptotic lower bound (i.e., $\Omega(n \log n)$). Are you absolutely sure the constant factor is 1? $\endgroup$ – dkaeae May 20 at 11:40
-2
$\begingroup$

If you can test algorithm, test it on all number combinations. If you have lot of number, test on lot of random combinations. Not precise, but faster than all combinations.

Minimal
a < b < c = 2
a < b < c < d = 3
a < b < c < d < e = 4

Maximal
3^3
4^4
5^5

Insert to middle use 3-6 for 4 numbers.
Merging use 4-5 for 4 numbers.
Minimal compare by wiki is 5 for 4 numbers :) For 5 is 7. You use 8, still so much.
https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
If you know all before comparations, you can go down with comparations. My average for 4 numbers is 3.96 / 1024 all combinations.

$\endgroup$
  • 1
    $\begingroup$ This doesn't answer the question. The question asks how to prove that there is no way to sort using only 7 comparisons. To use your approach, we'd have to enumerate all algorithms that use at most 7 comparisons. I think there are too many such algorithms to enumerate in a reasonable amount of time. In any case, I don't see what this adds over the existing answer, which already gave a complete answer to the question. We'd prefer that you focus on answering questions where you can add something new. $\endgroup$ – D.W. Feb 6 '18 at 13:43
  • $\begingroup$ Add is graphic and tip for alg. for predict cmp value from before cmp. And his min is 7, other sources 8, true min. is 4!!! 4 is work only for asc/desc order. Ex1: 00000 01234 43210 10000 ... Ex2: Insert to middle: 43210, start 4, get 3, cp 4>3, get 2, cp 4>2, cp 3>3, get 1, cp(mid) 3>1, cp 2>1, get 0, cp(mid) 3>0, cp 2>0, cp 1>0... 8 cmp. 7 can be possible for conncrete order or alg. You can look on my page for 4 numbers mlich.zam.slu.cz/js-sort/x-sort-x2.htm , Average 3.96. min-max 3-6. Can change for 5 and test his alg. $\endgroup$ – Peter Mlich Feb 8 '18 at 11:23

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.