Develop an efficient algorithm for sorting 5 different keys in less than 8 comparisons

Question

Create an efficient algorithm to sort 5 separate - very large - keys with less than 8 comparisons in the worst case. You cannot use radix collation.

Answer 1

Compare A with B and C with D. WLOG, suppose A> B and C> D. Compare A with C. WLOG, suppose A> C. Sort E into ACD. This can be done using two comparisons. Sort B into {E, C, D}. This can be done using two comparisons, a total of seven.

Answer 2

This is a beta response based pseudo code. Perhaps I have some mistakes, as I did it in a hurry.

if (A > B) swap A, B if (C > D) swap C, D if (A > C) swap A, C swap B, D # Thanks Deqing! if (E > C) if (E > D) %ACDE if (B > D) if (B > E) return (A, C, D, E, B) else return (A, C, D, B, E) else if (B < C) return (A, B, C, D, E) else return (A, C, B, D, E) else %ACED if (B > E) if (B > D) return (A, C, E, D, B) else return (A, C, E, B, D) else if (B < C) return (A, B, C, E, D) else return (A, C, B, E, D) else if (E < A) % EACD if (B > C) if (B > D) return (E, A, C, D, B) else return (E, A, C, B, D) else return (E, A, B, C, D) else %AECD if (B > C) if (B > D) return (A, E, C, D, B) else return (A, E, C, B, D) else if (B < E) return (A, B, E, C, D) else return (A, E, B, C, D) 

Answer 3

Five elements can be sorted with seven comparisons in the worst cast, because log ₂ (5!) = 6.9. I suggest checking if any standard sorting sorting algorithm achieves this number - if it shouldn't be difficult to hard-code the comparison sequence because of the small number of comparisons required.

I suggest writing a program to find a comparison sequence. Create a list with all 120 permutations of numbers from one to five. Then try all ten possible comparisons and choose the one that splits the list as best as possible in two lists of the same size. Perform this split and apply the same procedure to the two lists recursively.

I wrote a small program to do this, and here is the result.

 Comparison 1: 0-1 [60|60] // First comparison item 0 with item 1, splits case 60/60 Comparison 2: 2-3 [30|30] // Second comparison for the first half of the first comparison Comparison 3: 0-2 [15|15] // Third comparison for the first half of the second comparison for the first half of first comparison Comparison 4: 2-4 [8|7] Comparison 5: 3-4 [4|4] Comparison 6: 1-3 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 6: 1-4 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 5: 0-4 [4|3] Comparison 6: 1-2 [2|2] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 6: 1-2 [1|2] Comparison 7: 1-3 [1|1] Comparison 4: 0-4 [8|7] Comparison 5: 1-4 [4|4] Comparison 6: 1-3 [2|2] Comparison 7: 3-4 [1|1] Comparison 7: 0-3 [1|1] Comparison 6: 3-4 [2|2] Comparison 7: 0-3 [1|1] Comparison 7: 1-3 [1|1] Comparison 5: 0-3 [4|3] Comparison 6: 1-3 [2|2] Comparison 7: 2-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 6: 2-4 [2|1] Comparison 7: 3-4 [1|1] Comparison 3: 0-3 [15|15] // Third comparison for the second half of the second comparison for the first half of first comparison Comparison 4: 3-4 [8|7] Comparison 5: 2-4 [4|4] Comparison 6: 1-2 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 6: 1-4 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 5: 0-4 [4|3] Comparison 6: 1-3 [2|2] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 6: 1-2 [2|1] Comparison 7: 1-3 [1|1] Comparison 4: 0-4 [8|7] Comparison 5: 1-4 [4|4] Comparison 6: 1-2 [2|2] Comparison 7: 2-4 [1|1] Comparison 7: 0-2 [1|1] Comparison 6: 2-4 [2|2] Comparison 7: 0-2 [1|1] Comparison 7: 1-2 [1|1] Comparison 5: 0-2 [4|3] Comparison 6: 1-2 [2|2] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 6: 2-4 [1|2] Comparison 7: 3-4 [1|1] Comparison 2: 2-3 [30|30] // Second comparison for the second half of the first comparison Comparison 3: 0-3 [15|15] Comparison 4: 0-4 [7|8] Comparison 5: 0-2 [3|4] Comparison 6: 2-4 [2|1] Comparison 7: 3-4 [1|1] Comparison 6: 1-2 [2|2] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 5: 1-4 [4|4] Comparison 6: 2-4 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 0-2 [1|1] Comparison 6: 1-2 [2|2] Comparison 7: 0-2 [1|1] Comparison 7: 2-4 [1|1] Comparison 4: 3-4 [7|8] Comparison 5: 0-4 [3|4] Comparison 6: 1-2 [1|2] Comparison 7: 1-3 [1|1] Comparison 6: 1-3 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 5: 2-4 [4|4] Comparison 6: 1-4 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 6: 1-2 [2|2] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 3: 0-2 [15|15] Comparison 4: 0-4 [7|8] Comparison 5: 0-3 [3|4] Comparison 6: 2-4 [1|2] Comparison 7: 3-4 [1|1] Comparison 6: 1-3 [2|2] Comparison 7: 2-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 5: 1-4 [4|4] Comparison 6: 3-4 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 0-3 [1|1] Comparison 6: 1-3 [2|2] Comparison 7: 0-3 [1|1] Comparison 7: 3-4 [1|1] Comparison 4: 2-4 [7|8] Comparison 5: 0-4 [3|4] Comparison 6: 1-2 [2|1] Comparison 7: 1-3 [1|1] Comparison 6: 1-2 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 5: 3-4 [4|4] Comparison 6: 1-4 [2|2] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 6: 1-3 [2|2] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] 

But now the question is how to effectively implement this. Perhaps a lookup table could be used to store the comparison sequence. I'm also not sure how to effectively derive ordered output from this comparative sequence.

Sorting the result from above by comparison shows the obvious structure for the first comparisons, but with an increase in the number of comparisons it becomes more difficult. All blocks are symmetrical about the middle, indicated by the symbol ----- .

 Comparison 1: 0-1 [60|60] Comparison 2: 2-3 [30|30] Comparison 2: 2-3 [30|30] Comparison 3: 0-2 [15|15] Comparison 3: 0-3 [15|15] ----- Comparison 3: 0-3 [15|15] Comparison 3: 0-2 [15|15] Comparison 4: 2-4 [8|7] Comparison 4: 0-4 [8|7] Comparison 4: 3-4 [8|7] Comparison 4: 0-4 [8|7] ----- Comparison 4: 0-4 [7|8] Comparison 4: 3-4 [7|8] Comparison 4: 0-4 [7|8] Comparison 4: 2-4 [7|8] Comparison 5: 3-4 [4|4] Comparison 5: 0-4 [4|3] Comparison 5: 1-4 [4|4] Comparison 5: 0-3 [4|3] Comparison 5: 2-4 [4|4] Comparison 5: 0-4 [4|3] Comparison 5: 1-4 [4|4] Comparison 5: 0-2 [4|3] ----- Comparison 5: 0-2 [3|4] Comparison 5: 1-4 [4|4] Comparison 5: 0-4 [3|4] Comparison 5: 2-4 [4|4] Comparison 5: 0-3 [3|4] Comparison 5: 1-4 [4|4] Comparison 5: 0-4 [3|4] Comparison 5: 3-4 [4|4] Comparison 6: 1-3 [2|2] Comparison 6: 1-4 [2|2] Comparison 6: 1-2 [2|2] Comparison 6: 1-2 [1|2] Comparison 6: 1-3 [2|2] Comparison 6: 3-4 [2|2] Comparison 6: 1-3 [2|2] Comparison 6: 2-4 [2|1] Comparison 6: 1-2 [2|2] Comparison 6: 1-4 [2|2] Comparison 6: 1-3 [2|2] Comparison 6: 1-2 [2|1] Comparison 6: 1-2 [2|2] Comparison 6: 2-4 [2|2] Comparison 6: 1-2 [2|2] Comparison 6: 2-4 [1|2] ----- Comparison 6: 2-4 [2|1] Comparison 6: 1-2 [2|2] Comparison 6: 2-4 [2|2] Comparison 6: 1-2 [2|2] Comparison 6: 1-2 [1|2] Comparison 6: 1-3 [2|2] Comparison 6: 1-2 [2|2] Comparison 6: 1-4 [2|2] Comparison 6: 2-4 [1|2] Comparison 6: 1-3 [2|2] Comparison 6: 3-4 [2|2] Comparison 6: 1-3 [2|2] Comparison 6: 1-2 [2|1] Comparison 6: 1-2 [2|2] Comparison 6: 1-4 [2|2] Comparison 6: 1-3 [2|2] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 0-3 [1|1] Comparison 7: 0-3 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 0-2 [1|1] Comparison 7: 0-2 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] ----- Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 0-2 [1|1] Comparison 7: 0-2 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 2-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 0-3 [1|1] Comparison 7: 0-3 [1|1] Comparison 7: 3-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-3 [1|1] Comparison 7: 1-2 [1|1] Comparison 7: 1-4 [1|1] Comparison 7: 1-2 [1|1] 

Answer 4

This should be 7 or more comparisons.

There are 120 (5 factorials) ways to place 5 objects. An algorithm using 6 comparisons can only distinguish 2 ^ 6 = 64 different initial arrangements, so algorithms using 6 or less comparisons cannot sort all possible inputs.

There may be a sorting method using only 7 comparisons. If you only want to sort 5 elements, such an algorithm can be found (or proved not to exist) by brute force.

Answer 5

According to Wikipedia :

Determining the exact number of comparisons needed to sort a given number of records is a difficult task, even for small n, and there is no simple formula for the solution. "

Presumably, this means that there is no known acceptable (efficient) algorithm for determining exactly the optimal sorting.

Answer 6

Sort networks have a limited structure, so do not answer the original question; but they are funny. The sorting network list generates good diagrams or SWAP lists for up to 32 inputs. For 5 he gives

 There are 9 comparators in this network, grouped into 6 parallel operations. [[0,1],[3,4]] [[2,4]] [[2,3],[1,4]] [[0,3]] [[0,2],[1,3]] [[1,2]] 

Answer 7

I wrote a C-implementation of the solution to this problem, which can be found here: Sorting 5 elements using 7 comparisons

My code is well commented with an explanation of why it works.

Answer 8

An example of a sequence of operations using mergesort (below the merge function, it combines two sorted sublists into one sorted combined list):

 elements[1..2] <- merge(elements[1..1], elements[2..2]) # 1 comparison elements[3..4] <- merge(elements[3..3], elements[4..4]) # 1 comparison elements[3..5] <- merge(elements[3..4], elements[5..5]) # 1-2 comparisons elements[1..5] <- merge(elements[1..2], elements[3..5]) # 2-4 comparisons 

Answer 9

 Abcde

 A
 |  CDE - 1 Comparison
 B

 AC
 |  |  E - 1 Comparison
 Bd

   A
  / \
 BCE - 1 Comparison
      \
       D

E 3 comparisons are required. It should be compared with A , C , D

Try ACDE in this order.

In total, there will be nine comparisons - not very effective.

Answer 10

Others stated that there are 5! = 120 arrangements (permutations) to process, so you need 7 comparisons. To identify the permutation, in principle, you can build a large nested if expression in the form of 7 comparisons. Having determined the permutation, a pre-calculated swap / rotation sequence can be applied.

The first problem is that the choice of the second comparison depends on the result of the first comparison, etc. The trick at each stage is to choose a good comparison to divide the current set of possible permutations into two equal subsets. The easiest approach is to evaluate the split that will be achieved in each comparison until you find the right balance. Get out early if you find the perfect balance, but keep in mind that the perfect balance is not always possible, since we do not have exactly 2 ^ 7 = 128 permutations - in some cases (I assume 8) we only need six comparisons.

The second problem is to develop swap / rotation sequences for each of the 120 possible permutations, and possibly for dynamic programming. An if-I-do-this recursive search is probably required, the next result is that then the game tree recursion, and you really have to cache the IOW intermediate results. Too tired to find out the details of the ATM, sorry.

You can put all the steps in a digraph that turns off (identifying the permutation) and then returns the fans (applying each reordering step). Then, probably run it using the digraph minimization algorithm.

Wrap this in a code generator and you're done - your own 5 item sorter algorithmically close to perfection. The digraph type implies gotos in the generated code (especially if you minimize it), but people tend to turn a blind eye to this in the generated code.

Of course, all this is a little brute force, but why worry about elegance and efficiency - the likelihood that you will run a working generator only in any case, and the size of the problem is small enough to be achievable (although probably not if you are independent of naive "game tree" searches for each permutation).

Answer 11

FWIW, here's a compact and easy-to-use version of Python with tests to make sure it works:

 def sort5(a, b, c, d, e): 'Sort 5 values with 7 Comparisons' if a < b: a, b = b, a if c < d: c, d = d, c if a < c: a, b, c, d = c, d, a, b if e < c: if e < d: pass else: d, e = e, d else: if e < a: c, d, e = e, c, d else: a, c, d, e = e, a, c, d if b < d: if b < e: return b, e, d, c, a else: return e, b, d, c, a else: if b < c: return e, d, b, c, a else: return e, d, c, b, a if __name__ == '__main__': from itertools import permutations assert all(list(sort5(*p)) == sorted(p) for p in permutations(range(5))) 

Answer 12

It is impossible to have less than 9 comparisons to sort 5 items when input is unknown. The lower bound has been proven for sorting networks to 10. See https://en.wikipedia.org/wiki/Sorting_network .

The correct sorting of networks can be verified using the Zero-One principle, as mentioned in The Art of Computer Programming, Volume 3, by Knuth. That is, if the sorting network can correctly sort all permutations 0 and 1, then this is the correct sorting network. None of the algorithms mentioned in this post have passed the Zero-one test.

In addition, the lower bound indicates that comparison-based sorts cannot have less than ceil (log (n!)) Comparators for proper sorting, however this does not mean that this is achievable.