Ordenar una matriz con un número mínimo de comparaciones

Question

Necesito ayuda con mi tarea de CS. Necesito escribir una rutina de clasificación que ordene una matriz de longitud 5 usando 7 comparaciones en el peor de los casos (he demostrado que se necesitarán 7, debido a la altura del árbol de decisión).

Consideré usar el árbol de decisión 'codificado', pero eso significa que el algoritmo es realmente complicado y mi tutor ha insinuado que no es la forma en que se supone que debe hacerse.

He comprobado quicksort, merge sort, heap sort, d-ary heap sort, insertion sort, selection sort, all no responden al requisito, lo que me lleva a creer que hay una necesidad de un algoritmo específico para matrices de longitud 5.

Realmente me gustaría obtener algunas pistas en la dirección correcta.

Answer 1

Sí, está en Knuth vol 3 página 185 (sección 5.3.1). ¡Esto fue documentado por primera vez en una tesis de doctorado, por lo que su profesor está siendo muy duro con usted! No hay un método elegante realmente simple; tienes que rastrearlo como un árbol parcialmente ordenado.

Aquí está en lisp. Probado OK (SBCL en Linux)

(defun small-sort (a) 
    "Sort a vector A of length 5" 
    (if (> (aref a 0) (aref a 1)) 
     (rotatef (aref a 0) (aref a 1))) 
    (if (> (aref a 2) (aref a 3)) 
     (rotatef (aref a 2) (aref a 3))) 
    (if (> (aref a 0) (aref a 2)) 
     (progn 
     (rotatef (aref a 0) (aref a 2)) 
     (rotatef (aref a 1) (aref a 3)))) 
    (if (> (aref a 4) (aref a 2)) 
     (if (> (aref a 4) (aref a 3)) 
      (progn) 
      (rotatef (aref a 3) (aref a 4))) 
     (if (> (aref a 4) (aref a 0)) 
      (rotatef (aref a 2) (aref a 4) (aref a 3)) 
      (rotatef (aref a 0) (aref a 4) (aref a 3) (aref a 2)))) 
    (if (> (aref a 1) (aref a 3)) 
     (if (> (aref a 1) (aref a 4)) 
      (rotatef (aref a 1) (aref a 2) (aref a 3) (aref a 4)) 
      (rotatef (aref a 1) (aref a 2) (aref a 3))) 
     (if (> (aref a 1) (aref a 2)) 
      (rotatef (aref a 1) (aref a 2)) 
      (progn))) 
    a) 

(defun check-sorted (a) 
    (do ((i 0 (1+ i))) 
     ((>= i (1- (array-dimension a 0)))) 
    ;;(format t "~S ~S~%" (aref a i) (aref a (+ 1 i))) 
    (assert (<= (aref a i) (aref a (+ 1 i)))))) 

(defun rr() 
    (dotimes (i 100000) 
    (let ((a (make-array 5 :initial-contents (list (random 1.0) (random 1.0) (random 1.0) (random 1.0) (random 1.0))))) 
     ;;(format t "A=~S~%" a) 
     (let ((res (small-sort a))) 
     (check-sorted res) 
     ;;(format t "Res=~S~%" res) 
     )))) 

Answer 2

Eche un vistazo a la clasificación por cubo.

Answer 3

7 suena como podría ser shell ordenar también.

Answer 4

No creo que la solución no modificable tiene que ser tan complicado:

1. Comparar (elementos) 2 & 3 y cambie si es necesario
2. comparación 3 & 4, y de intercambio si requerido
3. Comparación 1 & 3, si 1 es menor, luego compare 1 & 2, de lo contrario compare 1 & 4. Coloque 1 en la ranura correcta.
4. Repita el paso 3, excepto con los elementos 3 & 5.

que siempre va a utilizar 7 comparaciones.

EDIT:

No creo que esto va a funcionar: Paso 4 se rompe, y podrían requerir una octava comparación. Considere:

Index | 1 | 2 | 3 | 4 | 5 | 
Value | 2 | 3 | 4 | 5 | 1 | 

Paso 4:

1. comparación 3 & 5 == 4 vs 1 == elemento 5 de menos de elemento 3
2. comparación 2 & 5 == 3 vs elemento 1 == 5 menos que el elemento 2
3. ??? Necesitará comparar 1 & 5 saber elemento 5.

Answer 5

Donald Knuth de El Arte de la Programación de Computadoras, volumen 3 tiene una sección sobre este tema exactamente dónde poner. No tengo los libros aquí conmigo, pero estoy bastante seguro de que Knuth presenta el algoritmo para 5 elementos. Como sospecha, no existe un algoritmo general que proporcione el número mínimo de comparaciones para muchos tamaños, pero hay una serie de trucos comunes que se utilizan en dichos algoritmos.

De recuerdos vagos, reconstruí el algoritmo para 5 elementos, y se puede hacer en 7 comparaciones. Primero, toma dos pares separados, compara los que están dentro de ellos y compara los más pequeños de cada par. Luego, compara el restante con el más grande de estos.Esto ahora se divide en dos casos según si el elemento restante fue más pequeño o más grande, pero en todos los casos es posible finalizar en las tres comparaciones disponibles.

Recomiendo hacer dibujos para ayudarlo. fotos de Knuth son algo como esto:

 
    o---o 
/
o---o 

que muestra los resultados después de las tres primeras comparaciones (y de lo que recuerdo, este tipo de una imagen aparece en muchos tipos mínimos de comparación). Una línea conecta dos elementos cuyo orden conocemos. Tener tales imágenes lo ayuda a determinar con qué elementos comparar, ya que quiere hacer una comparación que le proporcione la cantidad máxima de información.

Addendum: Como hay una respuesta aceptada con el código actual, supongo que no hay nada malo en terminar estos diagramas, y podrían ser una adición útil a la respuesta. Por lo tanto, comience con el anterior y compare el elemento que falta con el de la esquina superior izquierda. Si es mayor, esto conducirá a

 
    /--o 
    o 
/\--o 
o 
    \--o 

Ahora, comparar los dos elementos de grandes dimensiones en la parte superior derecha y nos encontramos con

 
    o---o---o 
/
o---o 

Ahora, comparando el elemento inferior derecha primero contra el medio en la parte superior y luego contra cualquier lado al que pertenezca, lo colocamos correctamente usando las dos comparaciones restantes.

Si la comparación inicial dio como resultado el elemento restante es más pequeño, se convierte en el diagrama

 
o---o---o 
    /
    o---o 

Ahora, compare las dos que tienen sin embargo, nada más pequeño que ellos. Una opción es el último diagrama anterior, que se puede resolver con las dos comparaciones restantes. El otro caso es

 
     o---o 
    /
o---o---o 

Y aquí de nuevo, el que todavía no está en secuencia con los otros pueden ser colocados correctamente con dos comparaciones.

Answer 6

cubo especie puede ser implementado como un algoritmo de comparación de la siguiente manera:

Tome un elemento.

Compárelo con todos los cucharones.

Colóquelo en el cucharón que coincida. < - Comparación necesaria.

Si no se encuentra la cubeta, cree una nueva cubeta.

Por lo tanto, es un algoritmo dinámico de clasificación de cubeta que acabo de describir.

Ya inventé/describí esto en un grupo de noticias en el pasado.