Ordenar una matriz de 5 enteros con un máximo de 7 comparaciones

19

¿Cómo puedo ordenar una lista de 5 enteros de modo que en el peor de los casos se necesitan 7 comparaciones? No me importa cuántas otras operaciones se realizan. No sé nada en particular sobre los enteros.

He intentado algunos enfoques diferentes de dividir y conquistar que me llevan a 8 comparaciones, como seguir un enfoque de combinación o combinar combinación con el uso de búsqueda binaria para encontrar la posición de inserción, pero cada vez que termino con 8 compara el peor de los casos .

En este momento solo estoy buscando una pista, no una solución.

Robert S. Barnes
fuente
¿Has intentado escribir el árbol "comparar con"? Tiene hojas, cada una correspondiente a una permutación de los enteros. Si no sabe a qué me refiero con el árbol "comparar", ¿conoce la prueba de que necesita n log n comparaciones? Ps, ¿qué te hace pensar que es posible? 5!=120nlogn
Pål GD
1
Bueno, en el complemento dos de 8 bits, if(x > y)es el mismo if((x - y) & 0x80)que difícilmente se puede comparar. Supongo que deberíamos olvidar que los objetos son enteros y asumir que debemos usar alguna compare(x, y)función mágica para comparar esos objetos ...
Karolis Juodelė
2
¿La "sección 5.3 sobre clasificación óptima en el Volumen 3 de The Art Of Computer Programming , que cubre precisamente esta pregunta" cuenta como una pista o una solución? :-)
Steven Stadnicki
3
El límite es realmente que y 5 ! = 120 < 2 7 = 128 . Entonces es posible (en principio). 2cn!5!=120<27=128
vonbrand

Respuestas:

23

Solo hay una forma de comenzar este proceso (y para casi todas sus decisiones sobre qué comparar en los pasos posteriores, solo hay una correcta). Aquí se explica cómo resolverlo. Primero, tenga en cuenta que hay respuestas posibles que puede obtener para sus comparaciones, ¡y 5 ! = 120 permutaciones diferentes entre las que necesita distinguir.27=1285!=120

La primera comparación es fácil: tienes que comparar dos claves, y como no sabes nada sobre ellas, todas las opciones son igualmente buenas. Así que digamos que se compara y B , y encuentra que un b . Ahora tiene 2 6 = 64 respuestas posibles restantes, y 60 permutaciones posibles restantes (ya que hemos eliminado la mitad de ellas).abab26=6460

A continuación, se puede comparar bien y d , o podemos comparar C a una de las claves que se utilizó en la primera comparación. Si comparamos C y D , y aprender que c d , entonces tenemos 32 respuestas restantes y 30 permutaciones posibles. Por otro lado, si comparamos c con una , y se descubre que un c , tenemos 40 posibles permutaciones restantes, porque hemos eliminado 1 / 3 de las posibles permutaciones (aquellos con c cdccdcd3230caac401/3 ). Solo tenemos 32 posibles respuestas restantes, así que no tenemos suerte.cab32

Entonces, ahora sabemos que tenemos que comparar las teclas primera y segunda, y las teclas tercera y cuarta. Podemos suponer que tenemos y c d . Si comparamos correo a cualquiera de estas cuatro teclas, por el mismo argumento que se utilizó en el paso anterior, podríamos eliminar solamente 1 / 3 de los restantes permutaciones, y estamos de suerte. Entonces tenemos que comparar dos de las claves a , b , c , d . Teniendo en cuenta la simetría, tenemos dos opciones, comparar a y c o comparar a y dabcde1/3a,b,c,dacad. Un argumento espectáculos similares recuento hay que comparar y c . Podemos suponer sin pérdida de generalidad que a c , y ahora tenemos a b y a c d .acacabacd

Como me pidió una pista, no analizaré el resto del argumento. Te quedan cuatro comparaciones. Úsalos sabiamente.

Peter Shor
fuente
ac
1
abaca,b,ca<b<ca<c<bde
8

{a,b,c,d,e}

  • (a,b),(c,d)
  • a<b,c<d
  • a<c
  • ec
    • e<c
    • e>c{b,c,d,e}c<e,c<d
      • Compare(d,e)d<e
        • Compare(b,d)b>d
          • Compare(b,e)
        • b<d
          • Compare(b,c)
      • d>e
        • Compare(b,e)b>e
          • Compare(b,d)
        • b<e
          • Compare(b,c)

ec

Jorge
fuente
¿Estas seguro que esto es correcto? Suponga que obtiene los siguientes resultados: a <b, c <d, a <c y luego c <e, b <e, c <b y d <e. Los ordenamientos a <c <b <d <e y a <c <d <b <e son ambos consistentes con ellos. La razón es que byd nunca se comparan, implícita o explícitamente. Tal vez me equivoque en alguna parte, si es así, corrígeme.
George