24
$\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?

Improve this question
$\endgroup$
32
$\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)
Improve this answer
$\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
1
$\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.

Improve this answer
$\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 '19 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 Aug 24 '19 at 15:16
-1
$\begingroup$

Some problems are that the question is (1)incompletely stated, and (2)includes unwarranted presumptions:

how can I prove that it can't be done in 7 comparisons?

On the first point, it is unclear what the domain of the sorting problem is: is it random real numbers (with some specified or unspecified distribution), or integers (in some specified or unspecified range), or some other type of objects; are the values guaranteed to be distinct, or could there be duplicates (triplicates, etc.), and so on? If there are duplicates, etc., does it matter whether the partial ordering of items which compare equal is maintained (a.k.a. stable sorting)? None of these things are specified, and they all affect possible (and/or inapplicable) potential solutions to the sorting problem which is behind the stated question. It's also unclear whether the question is about best-case, average-case, or worst-case comparisons (under some specified conditions for some problem domain). And it's unclear whether anything other than comparisons (e.g. amount of data movement, partial-order stability as mentioned above, etc.) is a consideration.

On the second point, one of the responses notes Demuth's 7 comparison solution to non-stable sorting, so the question as stated is an impossible quest; one cannot in fact (correctly) prove the impossibility of something which is in fact possible.

So the short answer to the question as stated is "you can't" (in part because there is a 7 comparison solution to sorting 5 elements with certain constraints (and lacking others), and partly because the question and background do not specify any relevant constraints, details of the problem domain, etc.).

Improve this answer
$\endgroup$
-2
$\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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ How can a pile of 3 elements be sorted in 1 comparison? $\endgroup$ – xskxzr Aug 24 '19 at 3:26
  • $\begingroup$ what 3 element pile are you talking about? what i described above produces 2 piles of 2 elements after the first pass. $\endgroup$ – scottyc Sep 7 '19 at 18:57
  • $\begingroup$ I thought that you use a random element as pivot. How can you select the middle element as pivot in 4 comparisons? $\endgroup$ – xskxzr Sep 8 '19 at 3:33
  • $\begingroup$ that's not what i'm saying. from above "Since 5!=120 .... using a binary decision tree you can sort 5 items in 7 comparisons." the number of permutations of the elements is 120 but there must be a branch that has only 6 comparisons because a random sample running of quicksort took only 6 to do the job. one of the 120 permutations is for the sorted list. that branch could contain as few as 4 comparisons. $\endgroup$ – scottyc Sep 17 '19 at 23:18
-3
$\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.

Improve this answer
$\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.