Classificação por comparação - Comparison sort

A classificação de um conjunto de pesos não rotulados por peso usando apenas uma balança requer um algoritmo de classificação por comparação.

Uma classificação por comparação é um tipo de algoritmo de classificação que só lê os elementos da lista por meio de uma única operação de comparação abstrata (geralmente um operador "menor ou igual a" ou uma comparação de três vias ) que determina qual dos dois elementos deve ocorrer primeiro no lista final classificada. O único requisito é que o operador faça uma pré - encomenda total sobre os dados, com:

se a ≤ b e b ≤ c, então a ≤ c (transitividade)
para todo um e b , uma ≤ b ou b ≤ um ( conexidade ).

É possível que tanto a ≤ b quanto b ≤ a ; neste caso, qualquer um pode vir primeiro na lista classificada. Em uma classificação estável , a ordem de entrada determina a ordem de classificação neste caso.

Uma metáfora para pensar sobre os tipos de comparação é que alguém tem um conjunto de pesos não rotulados e uma balança . O objetivo é alinhar os pesos por ordem de peso, sem nenhuma informação, exceto aquela obtida colocando dois pesos na balança e vendo qual deles é mais pesado (ou se pesam o mesmo).

Exemplos

Quicksort em ação em uma lista de números. As linhas horizontais são valores dinâmicos.

Alguns dos tipos de comparação mais conhecidos incluem:

Limites de desempenho e vantagens de diferentes técnicas de classificação

Existem limites fundamentais para o desempenho dos tipos de comparação. Uma classificação de comparação deve ter um limite inferior de caso médio de Ω ( n log n ) operações de comparação, que é conhecido como tempo linear . Isso é uma consequência da informação limitada disponível apenas por meio de comparações - ou, em outras palavras, da vaga estrutura algébrica de conjuntos totalmente ordenados. Nesse sentido, mergesort, heapsort e introsort são assintoticamente ideais em termos do número de comparações que devem realizar, embora essa métrica ignore outras operações. As classificações de não comparação (como os exemplos discutidos abaixo) podem atingir o desempenho O ( n ) usando operações diferentes de comparações, permitindo-lhes contornar esse limite inferior (assumindo que os elementos são de tamanho constante).

As classificações de comparação podem ser executadas mais rapidamente em algumas listas; muitas classificações adaptativas , como classificação por inserção, são executadas em tempo O ( n ) em uma lista já classificada ou quase classificada. O limite inferior Ω ( n log n ) se aplica apenas ao caso em que a lista de entrada pode estar em qualquer ordem possível.

Medidas do mundo real de velocidade de classificação podem precisar levar em conta a capacidade de alguns algoritmos de usar de forma otimizada a memória de computador em cache relativamente rápida , ou o aplicativo pode se beneficiar de métodos de classificação onde os dados classificados começam a aparecer para o usuário rapidamente (e então a velocidade do usuário de leitura será o fator limitante) em oposição aos métodos de classificação, onde nenhuma saída está disponível até que toda a lista seja classificada.

Apesar dessas limitações, as classificações de comparação oferecem a vantagem prática notável de que o controle sobre a função de comparação permite a classificação de muitos tipos de dados diferentes e o controle preciso sobre como a lista é classificada. Por exemplo, inverter o resultado da função de comparação permite que a lista seja classificada ao contrário; e pode-se classificar uma lista de tuplas em ordem lexicográfica apenas criando uma função de comparação que compara cada parte em sequência:

function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
    if lefta ≠ righta
        return compare(lefta, righta)
    else if leftb ≠ rightb
        return compare(leftb, rightb)
    else
        return compare(leftc, rightc)

A notação ternária balanceada permite que as comparações sejam feitas em uma etapa, cujo resultado será "menor que", "maior que" ou "igual a".

As classificações de comparação geralmente se adaptam mais facilmente a ordens complexas, como a ordem dos números de ponto flutuante . Além disso, uma vez que uma função de comparação é escrita, qualquer classificação de comparação pode ser usada sem modificação; classificações sem comparação normalmente requerem versões especializadas para cada tipo de dados.

Essa flexibilidade, junto com a eficiência dos algoritmos de classificação de comparação acima em computadores modernos, levou a uma preferência generalizada por classificações de comparação na maioria dos trabalhos práticos.

Alternativas

Alguns problemas de classificação admitem uma solução estritamente mais rápida do que o limite $Ω (n log n)$ para classificação por comparação usando classificações não comparativas ; um exemplo é a classificação de inteiros , em que todas as chaves são inteiros. Quando as chaves formam um intervalo pequeno (em comparação com $n$ ), a classificação por contagem é um algoritmo de exemplo executado em tempo linear. Outros algoritmos de classificação de inteiros, como classificação de raiz , não são assintoticamente mais rápidos do que a classificação por comparação, mas podem ser mais rápidos na prática.

O problema de ordenar pares de números por sua soma também não está sujeito ao limite $Ω (n ² log n)$ (o quadrado resultante do emparelhamento); o algoritmo mais conhecido ainda leva tempo $O (n ² log n)$ , mas apenas $O (n ²)$ comparações.

Número de comparações necessárias para classificar uma lista

n	${\ displaystyle \ left \ lceil \ log _ {2} (n!) \ right \ rceil}$	Mínimo
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	10	10
7	13	13
8	16	16
9	19	19
10	22	22
11	26	26
12	29	30
13	33	34
14	37	38
15	41	42
16	45	45 ou 46
17	49	49 ou 50
18	53	53 ou 54
19	57	58
20	62	62
21	66	66
22	70	71

n	${\ displaystyle \ left \ lceil \ log _ {2} (n!) \ right \ rceil}$	${\ displaystyle n \ log _ {2} n - {\ frac {n} {\ ln 2}}}$
10	22	19
100	525	521
1 000	8 530	8 524
10.000	118 459	118 451
100 000	1 516 705	1 516 695
1 000 000	18 488 885	18 488 874

Acima: Uma comparação do limite inferior com o número mínimo real de comparações (de OEIS : A036604 ) necessário para classificar uma lista de n itens (para o pior caso). Abaixo: Usando a aproximação de Stirling , este limite inferior é bem aproximado por .

{\ displaystyle \ left \ lceil \ log _ {2} (n!) \ right \ rceil}

{\ displaystyle n \ log _ {2} n - {\ frac {n} {\ ln 2}}}

O número de comparações que um algoritmo de classificação por comparação requer aumenta em proporção ao , onde é o número de elementos a serem classificados. Este limite é assintoticamente estreito . ${\ displaystyle n \ log (n)}$ ${\ displaystyle n}$

Dada uma lista de números distintos (podemos supor isso porque esta é uma análise de pior caso), existem permutações fatoriais, exatamente uma das quais é a lista em ordem classificada. O algoritmo de classificação deve obter informações suficientes das comparações para identificar a permutação correta. Se o algoritmo sempre é concluído após a maioria das etapas, ele não pode distinguir mais do que casos porque as chaves são distintas e cada comparação tem apenas dois resultados possíveis. Portanto, ${\ displaystyle n}$ ${\ displaystyle f (n)}$ ${\ displaystyle 2 ^ {f (n)}}$

{\ displaystyle 2 ^ {f (n)} \ geq n!}

, ou equivalente

{\ displaystyle f (n) \ geq \ log _ {2} (n!).}

Ao observar os primeiros fatores de , obtemos ${\ displaystyle n / 2}$ ${\ displaystyle n! = n (n-1) \ cdots 1}$

{\ displaystyle \ log _ {2} (n!) \ geq \ log _ {2} \ left (\ left ({\ frac {n} {2}} \ right) ^ {\ frac {n} {2} } \ right) = {\ frac {n} {2}} {\ frac {\ log n} {\ log 2}} - {\ frac {n} {2}} = \ Theta (n \ log n). }

{\ displaystyle \ log _ {2} (n!) = \ Omega (n \ log n).}

Isso fornece a parte do limite inferior da reivindicação. Um limite melhor pode ser dado por meio da aproximação de Stirling .

Um limite superior idêntico resulta da existência de algoritmos que atingem esse limite no pior caso, como heapsort e mergesort .

O argumento acima fornece um limite inferior absoluto , em vez de apenas assintótico, para o número de comparações, a saber, comparações. Este limite inferior é bastante bom (pode ser aproximado dentro de uma tolerância linear por uma classificação de mesclagem simples), mas é conhecido por ser inexato. Por exemplo, mas o número mínimo de comparações para classificar 13 elementos provou ser 34. ${\ displaystyle \ left \ lceil \ log _ {2} (n!) \ right \ rceil}$ ${\ displaystyle \ left \ lceil \ log _ {2} (13!) \ right \ rceil = 33}$

Determinar o número exato de comparações necessárias para classificar um determinado número de entradas é um problema computacionalmente difícil, mesmo para n pequeno , e nenhuma fórmula simples para a solução é conhecida. Para alguns dos poucos valores concretos que foram calculados, consulte OEIS : A036604 .

Limite inferior para o número médio de comparações

Um limite semelhante se aplica ao número médio de comparações. Assumindo que

todas as chaves são distintas, ou seja, cada comparação dará a > b ou a < b , e
a entrada é uma permutação aleatória, escolhida uniformemente a partir do conjunto de todas as permutações possíveis de n elementos,

é impossível determinar em qual ordem a entrada está com menos do que $log 2 (n!)$ comparações em média.

Isso pode ser visto mais facilmente usando conceitos da teoria da informação . A entropia de Shannon de tal permutação aleatória é $log 2 (n!)$ Bits. Como uma comparação pode fornecer apenas dois resultados, a quantidade máxima de informações que ela fornece é de 1 bit. Portanto, após k comparações, a entropia restante da permutação, dados os resultados dessas comparações, é de pelo menos $log 2 (n!) - k$ bits em média. Para realizar a classificação, são necessárias informações completas, de modo que a entropia restante deve ser 0. Segue-se que k deve ser pelo menos $log 2 (n!)$ Em média.

O limite inferior derivado por meio da teoria da informação é expresso como 'limite inferior da teoria da informação'. O limite inferior da teoria da informação está correto, mas não é necessariamente o limite inferior mais forte. E, em alguns casos, o limite inferior da teoria da informação de um problema pode até estar longe do verdadeiro limite inferior. Por exemplo, o limite inferior de seleção da teoria da informação é enquanto as comparações são necessárias para um argumento adversário. A interação entre o limite inferior da teoria da informação e o limite inferior verdadeiro é muito semelhante a uma função de valor real limitando uma função inteira. No entanto, isso não é exatamente correto quando o caso médio é considerado. ${\ displaystyle \ left \ lceil \ log _ {2} (n) \ right \ rceil}$ ${\ displaystyle n-1}$

Para descobrir o que acontece durante a análise do caso médio, a chave é a que se refere 'média'? Em média sobre o quê? Com algum conhecimento da teoria da informação, as médias dos limites inferiores da teoria da informação sobre o conjunto de todas as permutações como um todo. Mas qualquer algoritmo de computador (sob o que se acredita atualmente) deve tratar cada permutação como uma instância individual do problema. Conseqüentemente, o limite inferior médio que procuramos é a média de todos os casos individuais.

Para pesquisar o limite inferior relacionado à impossibilidade de obtenção de computadores, adotamos o modelo de árvore de decisão . Vamos reformular um pouco o que é nosso objetivo. No modelo de árvore de decisão , o limite inferior a ser mostrado é o limite inferior do comprimento médio dos caminhos da raiz para a folha de uma árvore binária de folha (em que cada folha corresponde a uma permutação). Seria convencido dizer que uma árvore binária completa balanceada atinge o mínimo do comprimento médio. Com alguns cálculos cuidadosos, para uma árvore binária completa balanceada com folhas, o comprimento médio dos caminhos da raiz para a folha é dado por ${\ displaystyle n!}$ ${\ displaystyle n!}$

{\ displaystyle {\ frac {(2n! -2 ^ {\ lfloor \ log _ {2} n! \ rfloor +1}) \ cdot \ lceil \ log _ {2} n! \ rceil + (2 ^ {\ lfloor \ log _ {2} n! \ rfloor +1} -n!) \ cdot \ lfloor \ log _ {2} n! \ rfloor} {n!}}}

Por exemplo, para $n = 3$ , o limite inferior da teoria da informação para o caso médio é de aproximadamente 2,58, enquanto o limite inferior médio derivado por meio do modelo de árvore de decisão é 8/3, aproximadamente 2,67.

No caso em que vários itens podem ter a mesma chave, não há uma interpretação estatística óbvia para o termo "caso médio", portanto, um argumento como o acima não pode ser aplicado sem fazer suposições específicas sobre a distribuição de chaves.

Classificando uma lista pré-classificada

Se uma lista já estiver pré-classificada, o número de comparações necessárias para classificar a lista geralmente é menor. A noção de lista pré-ordenada pode ser formalizada com várias medidas de pré- ordenação . Dada essa medida , existe uma noção de algoritmo de classificação (fracamente) ótimo. ${\ displaystyle m}$ ${\ displaystyle m}$

Notas

^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introdução aos algoritmos (3ª ed.). MIT Press e McGraw-Hill. pp. 191–193. ISBN 0-262-03384-4 .
^ Mark Wells, Applications of a language for computing in combinatorics, Information Processing 65 (Proceedings of the 1965 IFIP Congress), 497-498, 1966.
^ Mark Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.
^ Takumi Kasai, Shusaku Sawato, Shigeki Iwata, Trinta e quatro comparações são necessárias para classificar 13 itens, LNCS 792, 260-269, 1994.
^ Marcin Peczarski, Sorting 13 elements needs 34 comparisons, LNCS 2461, 785-794, 2002.
^ ^a ^b ^c Marcin Peczarski, Novos resultados na classificação de comparação mínima, Algorithmica 40 (2), 133–145, 2004.
^ Marcin Peczarski, pesquisa assistida por computador dos posets, tese de doutorado, Universidade de Varsóvia, 2006.
^ Peczarski, Marcin (2007). "O algoritmo Ford-Johnson ainda está imbatível por menos de 47 elementos". Inf. Processar. Lett . 101 (3): 126–128. doi : 10.1016 / j.ipl.2006.09.001 .
^ ^a ^b Cheng, Weiyi; Liu, Xiaoguang; Wang, Gang; Liu, Jing (outubro de 2007). "最少比较排序问题中 S （15）和 S （19）的解决" [Os resultados de S (15) e S (19) para o problema de ordenação por comparação mínima]. Journal of Frontiers of Computer Science and Technology (em chinês). 1 (3): 305–313.
^ Peczarski, Marcin (3 de agosto de 2011). "Rumo à classificação ideal de 16 elementos". Acta Universitatis Sapientiae . 4 (2): 215–224. arXiv : 1108,0866 . Bibcode : 2011arXiv1108.0866P .

Referências

Donald Knuth . The Art of Computer Programming , Volume 3: Sorting and Searching , Second Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Seção 5.3.1: Classificação por comparação mínima, pp. 180–197.

[1] Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introdução aos algoritmos (3ª ed.). MIT Press e McGraw-Hill. pp. 191–193. ISBN 0-262-03384-4 .

[Wells1965-2] Mark Wells, Applications of a language for computing in combinatorics, Information Processing 65 (Proceedings of the 1965 IFIP Congress), 497-498, 1966.

[Wells1971-3] Mark Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.

[KasaiSawatoIwata1994-4] Takumi Kasai, Shusaku Sawato, Shigeki Iwata, Trinta e quatro comparações são necessárias para classificar 13 itens, LNCS 792, 260-269, 1994.

[Peczarski2002-5] Marcin Peczarski, Sorting 13 elements needs 34 comparisons, LNCS 2461, 785-794, 2002.

[Peczarski2004-6] Marcin Peczarski, Novos resultados na classificação de comparação mínima, Algorithmica 40 (2), 133–145, 2004.

[Peczarski2006-7] Marcin Peczarski, pesquisa assistida por computador dos posets, tese de doutorado, Universidade de Varsóvia, 2006.

[Peczarski2007-8] Peczarski, Marcin (2007). "O algoritmo Ford-Johnson ainda está imbatível por menos de 47 elementos". Inf. Processar. Lett . 101 (3): 126–128. doi : 10.1016 / j.ipl.2006.09.001 .

[ChengLiuWang2007-9] Cheng, Weiyi; Liu, Xiaoguang; Wang, Gang; Liu, Jing (outubro de 2007). "最少比较排序问题中 S （15）和 S （19）的解决" [Os resultados de S (15) e S (19) para o problema de ordenação por comparação mínima]. Journal of Frontiers of Computer Science and Technology (em chinês). 1 (3): 305–313.

[10] Peczarski, Marcin (3 de agosto de 2011). "Rumo à classificação ideal de 16 elementos". Acta Universitatis Sapientiae . 4 (2): 215–224. arXiv : 1108,0866 . Bibcode : 2011arXiv1108.0866P .

Languages

In other projects