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

¿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.

algorithms sorting 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

comparaciones? Ps, ¿qué te hace pensar que es posible?

5! = 120

$5! = 120$

n \log n

$n \log n$

Pål GD

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ė

¿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

El límite es realmente que

. Entonces es posible (en principio).

2^{c} \geq n!

$2^c \ge n!$

5! = 120 < 2^{7} = 128

$5! = 120 < 2^7 = 128$

vonbrand

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

Janus Troelsen

Respuestas:

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 permutaciones diferentes entre las que necesita distinguir. $2^7 =128$ $5! = 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 , y encuentra que . Ahora tiene respuestas posibles restantes, y permutaciones posibles restantes (ya que hemos eliminado la mitad de ellas). $a$ $b$ $a \leq b$ $2^6 = 64$ $60$

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

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

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

Peter Shor
fuente

a

$a$

c

$c$

a \leq b

$a \leq b$

a \leq c

$a \leq c$

a, b, c

$a,b,c$

a < b < c

$a < b < c$

a < c < b

$a < c < b$

d

$d$

e

$e$

$\{a,b,c,d,e\}$

$(a,b), (c,d)$
$a<b, c<d$
$a<c$
- $e<c$
- - - - $Compare(b,e)$
    - - $Compare(b,c)$
  - - - $Compare(b,d)$
    - - $Compare(b,c)$

$e$ $c$

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