Sort 5 items with minimal item comparison

Question

I need to simulate a execution plan for sorting a list of 5 elements in python using the minimum number of comparisons between elements. In addition, complexity does not matter.

The result is a list of pairs representing the comparisons needed to sort the list at another time.

I know there is an algorithm that does this in 7 comparisons (between elements, always, not complexity), but I can not find a readable (for me) version.

How can I sort 5 elements in 7 comparisons and build a “execution plan” for sorting?

PD: not homework.

Answer 1

This corresponds to the sorting description of 5 elements in 7 comparisons :

 import random n=5 ran=[int(n*random.random()) for i in xrange(n)] print ran def selection_sort(li): l=li[:] sl=[] i=1 while len(l): lowest=l[0] for x in l: if x<lowest: lowest=x sl.append(lowest) l.remove(lowest) print i i+=1 return sl print selection_sort(ran) 

It uses Selection Sort , which is NOT the most efficient, but uses very few comparisons.

This can be reduced to:

 def ss(li): l=li[:] sl=[] while len(l): sl.append(l.pop(l.index(min(l)))) return sl 

In any case, it prints something like this:

 [0, 2, 1, 1, 4] 1 2 3 4 5 [0, 1, 1, 2, 4] 

Perl has a wonderful module called Algorithm :: Networksort that allows you to play with them. The Bose-Nelson algorithm is quoted by Knut for several comparators, and you can see it here .

Edit

sorting insert also works well:

 def InsertionSort(l): """ sorts l in place using an insertion sort """ for j in range(1, len(l)): key = l[j] i = j - 1 while (i >=0) and (l[i] > key): l[i+1] = l[i] i = i - 1 l[i+1] = key 

Answer 2

Well, there are 5! = 120 ways to organize elements. Each comparison gives you one bit of information, so you need at least k comparisons, where 2 ^ k> = 120. You can check 2 ^ 7 = 128, so 7 is the least number of comparisons that you need to perform.

Answer 3

As a result, I used the usual sorting algorithm (insertion sorting) using a custom comparison operator that interrupts the sorting and gradually creates an execution plan to resume or replay the process.

It was ugly: the function threw an exception encapsulating the necessary information to continue sorting. Then the sorting can be repeated with new information, it may be canceled again.

As sorting attempts occur over a range of HTTP requests, performance is not a problem for me.