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.

Not what you were looking for, but I was curious, so I just checked: on the 120 permutations of range(5), the number of permutations for which the built-in `sorted` uses each number of comparisons are: 4: 2, 6: 5, 7: 33, 8: 56, 9: 24. — Danica, Jul 29 '12 at 04:01
Do the descriptions of the optimal algorithm given in the answers to [this question](http://stackoverflow.com/questions/1534748/design-an-efficient-algorithm-to-sort-5-distinct-keys-in-fewer-than-8-comparison) suffice? — DSM, Jul 29 '12 at 04:20

score 3 · Answer 1 · answered Jul 29 '12 at 04:09

3

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.

answered Jul 29 '12 at 04:09

Samuel Hapak

6,950
3
35
58

Beautiful math, but this is not answering my question =/ – salezica Jul 29 '12 at 05:40
So then what is your question? @uwop-episdn – msw Jul 29 '12 at 14:17
'**How can I** sort the 5 elements in 7 comparisons, and build an "execution plan" for the sort?'. It was written right there =/ – salezica Jul 31 '12 at 09:30

dawg · Accepted Answer · 2012-07-29T14:12:57.713

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

This is a misleading answer. I think your selection_sort function does 15 comparisons. First iteration, you compare lowest with 5 elements. Second iteration, lowest compared to 4 elements, and so on. So it would be 5 + 4 + 3 + 2 + 1 = 15 — Pangeran Bottor, Apr 12 '20 at 04:46

score 0 · Answer 3 · answered Jul 29 '12 at 12:59

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.

Sorting 5 elements with minimum element comparison

3 Answers3

Linked