Clasificando 5 elementos con una comparación mínima de elementos

Question

Tengo que modelar el plan de ejecución de ordenar una lista de 5 elementos, en python, usando el número mínimo de comparaciones entre elementos. Aparte de eso, la complejidad es irrelevante.

El resultado es una lista de pares que representa las comparaciones necesarias para ordenar la lista en otro momento.

Sé que hay un algoritmo que hace esto en 7 comparaciones (entre elementos, siempre, sin complejidad), pero no puedo encontrar una versión legible (para mí).

¿Cómo puedo ordenar los 5 elementos en 7 comparaciones, y crear un "plan de ejecución" para el género?

PD: no tarea.

Answer 1

Esto se adapte a su descripción de la clasificación 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) 

Este utiliza un Selection Sort que no es el más eficiente, pero qué utiliza muy pocas comparaciones.

Esto se puede acortar a:

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

En cualquier caso, imprime algo como esto:

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

Perl tiene un módulo encantador llamado Algorithm::Networksort que le permite jugar con estos. El algoritmo Bose-Nelson es citado por Knuth para pocos comparadores y puedes verlo here.

Editar

Un insertion sort también funciona bien:

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

Bueno, hay 5! = 120 formas en que se pueden ordenar los elementos. Cada comparación proporciona un bit de información, por lo que necesita al menos k comparaciones, donde 2^k> = 120. Puede verificar 2^7 = 128, por lo que el 7 es el número mínimo de comparaciones que debe realizar.

Answer 3

Terminé usando un algoritmo de ordenación regular (ordenación por inserción) con un operador de comparación personalizada que interrumpe la clasificación y progresivamente construye una ejecución planee reanudar o reproducir el proceso.

Era feo: la función generaba una excepción que encapsulaba la información necesaria para continuar la ordenación. Luego la ordenación podría reintentarse con la nueva información, para que probablemente sea abortada nuevamente.

Como los intentos de ordenación se producen a lo largo de las solicitudes http, el rendimiento no es un problema para mí.