21
$\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$
27
$\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
  • $\begingroup$ The theoretical lower bound for the worst case is ceil (log2 (n!)), because there are exactly n! permutations, and if there are k comparisons you need 2^k ≥ n!. It's not just a constant factor 1, it's exact. $\endgroup$ – gnasher729 15 hours ago
-1
$\begingroup$

i was thinking quicksort. you select as pivot the element that just happens to be the middle element. compare the pivot to the remaining 4 items resulting in two piles to be sorted. each of those piles can be sorted in 1 comparison. unless i have made a terrible mistake, the 5 items were fully sorted in just 6 comparisons and i think that is the absolute fewest number of comparisons needed to do the job. the original question was find the least number of comparisons to sort 5 elements.

New contributor
scottyc is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 1
    $\begingroup$ How can a pile of 3 elements be sorted in 1 comparison? $\endgroup$ – xskxzr yesterday
-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$
  • 2
    $\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.