Menor número de comparações necessárias para classificar (ordenar) 5 elementos

22

Encontre o menor número de comparações necessário para classificar (ordenar) cinco elementos e invente um algoritmo que classifique esses elementos usando esse número de comparações.

Solução : Existem 5! = 120 resultados possíveis. Portanto, uma árvore binária para o procedimento de classificação terá pelo menos 7 níveis. De fato, ≥ 120 implica h ≥ 7. Mas 7 comparações não são suficientes. O menor número de comparações necessárias para classificar (ordenar) cinco elementos é 8.2hh

Aqui está minha pergunta real: Encontrei um algoritmo que faz isso em 8 comparações, mas como posso provar que isso não pode ser feito em 7 comparações?

Por favor ajude
fonte

Respostas:

27

A solução está errada. Demuth [1; via 2, seg. 5.3.1] mostra que cinco valores podem ser classificados usando apenas sete comparações, ou seja, que o limite inferior "teórico da informação" é rígido nesse caso.

A resposta é um método adaptado para , não um algoritmo geral. Também não é muito agradável. Este é o esboço:n=5

  1. Classifique os dois primeiros pares.

  2. Ordene os pares por seu respectivo elemento maior.

    Chame o resultado ; sabemos a < b < d e c < d .[a,b,c,d,e]a<b<dc<d

  3. Insira em [ a , b , d ] .e[a,b,d]

  4. Insira no resultado da etapa 3.c

O primeiro passo leva claramente duas comparações, o segundo único. Os dois últimos passos fazem duas comparações cada; inserimos em uma lista de três elementos em ambos os casos (para a etapa 4., observe que sabemos de que c é menor que o último elemento da lista em questão) e comparamos primeiro com o elemento do meio. Isso totaliza sete comparações.c<dc

Como não vejo como escrever pseudocódigo "bom" disso, veja aqui uma implementação testada (e espero que seja legível).


  1. Ph.D. tese (Universidade de Stanford) de HB Demuth (1956)

    Veja também Classificação Eletrônica de Dados por HB Demuth (1985)

  2. Classificação e pesquisa de Donald E. Knuth; A arte da programação de computadores vol. 3 (2ª ed., 1998)
Rafael
fonte
5
O teste dá cinco pontos por mostrar que é impossível. Você quer saber quantos pontos você obteria pela sua resposta :-) (Provavelmente zero, pois o teste não pode estar errado).
gnasher729
0

O limite inferior teórico da classificação baseada em comparação é log(n!) . Ou seja, para classificar n itens usando apenas comparações < ou > é necessário pelo menos o logaritmo base 2 de n!, portanto, log(5!)6.91 operações.

Desde 5!=120 e 27=128 , usando uma árvore de decisão binária, você pode classificar 5 itens em 7 comparações. A árvore descobre exatamente qual das 120 permutações que você possui e realiza as trocas necessárias para classificá-la.

Não é um código bonito ou curto, e você provavelmente deve usar métodos de geração de código para criar a árvore de decisão e trocar em vez de codificá-lo manualmente, mas funciona; e provavelmente funciona para qualquer permutação possível de 5 itens, provando assim que você pode classificar 5 itens em não mais que 7 comparações.

Ron Peacetree
fonte
Ω(nlogn)
O limite inferior teórico para o pior caso é ceil (log2 (n!)), Porque existem exatamente n! permutações e, se houver k comparações, você precisará de 2 ^ k ≥ n !. Não é apenas um fator constante 1, é exato.
gnasher729 24/08
-1

eu estava pensando em quicksort. você seleciona como pivô o elemento que por acaso é o elemento do meio. compare o pivô com os 4 itens restantes, resultando em duas pilhas a serem classificadas. cada uma dessas pilhas pode ser classificada em 1 comparação. a menos que eu tenha cometido um erro terrível, os 5 itens foram totalmente classificados em apenas 6 comparações e acho que esse é o menor número absoluto de comparações necessárias para realizar o trabalho. a pergunta original era encontrar o menor número de comparações para classificar 5 elementos.

scottyc
fonte
1
Como uma pilha de 3 elementos pode ser classificada em 1 comparação?
xskxzr
de que pilha de 3 elementos você está falando? o que descrevi acima produz 2 pilhas de 2 elementos após a primeira passagem.
scottyc 7/09
Eu pensei que você usasse um elemento aleatório como pivô. Como você pode selecionar o elemento do meio como pivô em 4 comparações?
xskxzr 8/09
não é isso que estou dizendo. from above "Desde 5! = 120 .... usando uma árvore de decisão binária, você pode classificar 5 itens em 7 comparações." o número de permutações dos elementos é 120, mas deve haver um ramo que tenha apenas 6 comparações, porque uma amostra aleatória em execução do quicksort levou apenas 6 para fazer o trabalho. uma das 120 permutações é para a lista classificada. esse ramo pode conter apenas 4 comparações.
scottyc 17/09
-2

Se você pode testar o algoritmo, teste-o em todas as combinações de números. Se você tiver muitos números, teste em muitas combinações aleatórias. Não preciso, mas mais rápido que todas as combinações.

Mínimo
a <b <c = 2
a <b <c <d = 3
a <b <c <d <e = 4

Máximo
3 ^ 3
4 ^ 4
5 ^ 5

Insira no meio do uso 3-6 para 4 números.
Mesclando use 4-5 para 4 números.
A comparação mínima pelo wiki é de 5 para 4 números :) Para 5 é 7. Você usa 8, ainda muito.
https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
Se você souber tudo antes das comparações, poderá compará-las. Minha média para 4 números é 3,96 / 1024 todas as combinações.

Peter Mlich
fonte
2
Isso não responde à pergunta. A pergunta pergunta como provar que não há como classificar usando apenas 7 comparações. Para usar sua abordagem, teríamos que enumerar todos os algoritmos que usam no máximo 7 comparações. Eu acho que existem muitos desses algoritmos para enumerar em um período de tempo razoável. De qualquer forma, não vejo o que isso acrescenta à resposta existente, que já deu uma resposta completa à pergunta. Preferimos que você se concentre em responder perguntas, onde você pode adicionar algo novo.
DW
Add é gráfico e dica para alg. para prever o valor de cmp antes de cmp. E seu mínimo é 7, outras fontes 8, verdadeiro min. é 4 !!! 4 é trabalho apenas para ordem ascendente / descendente. Ex1: 00000 01234 43210 10000 ... Ex2: insira no meio: 43210, inicie 4, obtenha 3, cp 4> 3, obtenha 2, cp 4> 2, cp 3> 3, obtenha 1, cp (meados) 3> 1, cp 2> 1, obtenha 0, cp (médio) 3> 0, cp 2> 0, cp 1> 0 ... 8 cmp. 7 pode ser possível para ordem concreta ou alg. Você pode procurar na minha página 4 números mlich.zam.slu.cz/js-sort/x-sort-x2.htm , média 3,96. min-max 3-6. Pode mudar para 5 e testar seu alg.
Peter Mlich