Sorting 5 elements with minimum element comparison

问题:

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.

回答1:

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

回答2:

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.

回答3:

I ended up using a regular sorting algorithm (insertion sort) with a custom comparison operator that interrupts the sorting and progressively builds an execution plan to resume or reproduce the process.

It was ugly: the function raised an exception encapsulating the necessary information to continue sorting. Then sorting could be retried with the new information, to probably be aborted again.

As sorting attempts occur over the span of http requests, performance is not an issue for me.