Sorting 5 elements with minimum element comparison

Question

I have to model the execution plan of sorting a list of 5 elements, in python, using the minimum number of comparisons between elements. Other than that, the complexity is irrelevant.

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

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

How can I sort the 5 elements in 7 comparisons, and build an "execution plan" for the sort?

PD: not homework.

Answer 1

Well, there are 5!=120 ways how can elements be ordered. 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 the 7 is least number of comparisons you need to perform.

Answer 2

This fits your description of sorting 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)  

This uses a Selection Sort which is NOT the most efficient, but does use very few comparisons.

This can be shortened to:

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

In either case, prints something like this:

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

Perl has a lovely module called Algorithm::Networksort that allows you to play with these. The Bose-Nelson algorithm is cited by Knuth for few comparators and you can see it here.

Edit

An insertion sort 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