Ordinamento di 5 elementi con confronto di elementi minimi

Question

Devo modellare il piano di esecuzione di ordinare un elenco di 5 elementi, in python, utilizzando il numero minimo di confronti tra elementi. Oltre a ciò, la complessità è irrilevante.

Il risultato è un elenco di coppie che rappresentano i confronti necessari per ordinare l'elenco in un altro momento.

So che c'è un algoritmo che fa questo in 7 confronti (tra elementi, sempre, non complessità-saggio), ma non riesco a trovare una versione leggibile (per me).

Come posso ordinare i 5 elementi in 7 confronti e creare un "piano di esecuzione" per l'ordinamento?

PD: non compiti.

Answer 1

questo si inserisce la vostra descrizione di smistamento 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) 

Questo utilizza un Selection Sort che non è il più efficiente, ma fa uso di pochissimi paragoni.

questo può essere ridotto a:

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

In entrambi i casi, di stampare qualcosa di simile:

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

Perl ha un bel modulo chiamato Algorithm::Networksort che ti permette di giocare con questi. L'algoritmo di Bose-Nelson è citato da Knuth per pochi comparatori e puoi vederlo here.

Modifica

Un insertion sort funziona anche bene:

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

Bene, ci sono 5! = 120 modi in cui è possibile ordinare gli elementi. Ogni confronto ti dà un po 'di informazioni, quindi hai bisogno di almeno k confronti, dove 2^k> = 120. Puoi controllare 2^7 = 128, quindi il 7 è il numero minimo di confronti che devi eseguire.

Answer 3

ho finito per usare un algoritmo di ordinamento regolare (inserzione) con un operatore di confronto personalizzato che interrompe l'ordinamento e progressivamente costruisce un'esecuzione piano per riprendere o riprodurre il processo.

E 'stato brutto: la funzione ha sollevato un'eccezione che incapsula le informazioni necessarie per continuare l'ordinamento. Quindi l'ordinamento potrebbe essere ritentato con le nuove informazioni, probabilmente verrà di nuovo interrotto.

Poiché i tentativi di smistamento si verificano nell'arco delle richieste http, le prestazioni non rappresentano un problema per me.