Classifique uma matriz de 5 números inteiros com um máximo de 7 comparações

19

Como posso classificar uma lista de 5 números inteiros, de modo que, na pior das hipóteses, são necessários 7 comparações? Não ligo para quantas outras operações são executadas. Não sei nada de particular sobre os números inteiros.

Eu tentei algumas abordagens diferentes de dividir e conquistar, que me reduziram a 8 comparações, como seguir uma abordagem de mesclagem ou combinar mesclagem com o uso de pesquisa binária para encontrar a posição de inserção, mas toda vez que eu termino com 8 compara o pior caso .

No momento, estou apenas procurando uma dica, não uma solução.

Robert S. Barnes
fonte
Você já tentou escrever a árvore "comparar com"? Tem folhas, cada uma correspondendo a uma permutação dos números inteiros. Se você não sabe o que quero dizer com a árvore "comparar com", conhece a prova de que precisa de n log n comparações? Ps, o que faz você pensar que é possível? 5!=120nlogn
Pål GD 01/04
1
Bem, no complemento de 8 bits dois, if(x > y)é o mesmo if((x - y) & 0x80)que dificilmente se compara. Eu acho que nós devemos esquecer que os objetos são inteiros e assumir devemos usar alguma mágica compare(x, y)função para comparar os objetos ...
Karolis Juodelė
2
O 'check-out da seção 5.3 sobre classificação ideal no volume 3 de The Art Of Computer Programming , que cobre precisamente essa questão', conta como uma dica ou solução? :-)
Steven Stadnicki
3
O limite é realmente que e 5 ! = 120 < 2 7 = 128 . Então é possível (em princípio). 2cn!5!=120<27=128
vonbrand

Respostas:

23

Há apenas uma maneira de iniciar esse processo (e para quase todas as suas decisões sobre o que comparar nas etapas posteriores, existe apenas uma correta). Aqui está como descobrir isso. Primeiro, observe que existem respostas possíveis que você pode obter para suas comparações e 5 ! = 120 permutações diferentes que você precisa distinguir.27=1285!=120

A primeira comparação é fácil: você precisa comparar duas chaves e, como não sabe nada sobre elas, todas as opções são igualmente boas. Então, digamos que você comparar e b , e achar que a b . Agora você tem 2 6 = 64 respostas possíveis restantes e 60 permutações possíveis restantes (já que eliminamos metade delas).abab26=6460

Em seguida, podemos comparar e d , ou podemos comparar c a uma das chaves que usamos na primeira comparação. Se compararmos c e d , e aprender que c d , então temos 32 restantes respostas e 30 permutações possíveis. Por outro lado, se compararmos c com um , e descobrimos que uma c , temos 40 permutações possíveis restantes, porque temos eliminado 1 / 3 das permutações possíveis (aqueles com c cdccdcd3230caac401/3 ). Temos apenas 32 respostas possíveis, por isso estamos sem sorte.cab32

Então agora sabemos que temos que comparar a primeira e a segunda chaves e a terceira e quarta chaves. Podemos supor que temos e c d . Se compararmos e a qualquer uma destas quatro chaves, pelo mesmo argumento foi utilizado na etapa anterior, poderíamos só eliminar 1 / 3 das permutações remanescentes, e estamos sem sorte. Portanto, temos que comparar duas das teclas a , b , c , d . Considerando a simetria, temos duas opções: comparar a e c ou comparar a e dabcde1/3a,b,c,dacad. Um argumento de contagem semelhante mostra que devemos comparar e c . Podemos assumir sem perda de generalidade que a c , e agora temos um b e um c d .acacabacd

Desde que você pediu uma dica, eu não vou passar pelo resto da discussão. Você tem quatro comparações restantes. Use-os com sabedoria.

Peter Shor
fonte
Como você conseguiu que comparar a c reduz apenas 40 permutações? ac
Robert S. Barnes
1
@ Robert: Suponha que você tenha e um c . Então existem duas permutações de a , b , c consistentes com essas restrições, a < b < c e a < c < b . Para cada uma destas duas permutações, há quatro lugares que você pode adicionar d e cinco lugares que você pode adicionar e . abaca,b,ca<b<ca<c<bde
Peter Shor
8

Você pode encontrar isso em The Art of Computer Programming vol III, de D.Knuth, mas a estratégia é a seguinte (presumo que você tenha o array ): Se você quiser ler as dicas apenas duas primeiras linhas da minha resposta{a,b,c,d,e}

  • Primeiro grupo de pares de números: .(a,b),(c,d)
  • Compare os pares para ordená-los, por exemplo: .a<b,c<d
  • Compare os menores elementos de pares, obtemos resultado, por exemplo, .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

George
fonte
Tem certeza de que isso está correto? Suponha que você obtenha os seguintes resultados: a <b, c <d, a <ce depois c <e, b <e, c <b e d <e. Os pedidos a <c <b <d <e e a <c <d <b <e são ambos consistentes com eles. A razão é que b e d nunca são comparados, implícita ou explicitamente. Talvez eu esteja enganado em algum lugar, se sim, por favor me corrija.
George #