Ordenação por comparação

Um algoritmo de comparação é um tipo de algoritmo de ordenação que lê apenas os elementos da lista através de uma operação de comparação abstrata única (muitas vezes um operador "menor ou igual a"), que determina qual dos dois elementos devem ocorrer em primeiro lugar na lista final de classificação. A única exigência é que o operador cumpra a duas das propriedades de uma ordem total:

se a ≤ b e b ≤ c então a ≤ c (transitividade)
para todo a e b, ou a ≤ b ou b ≤ a (totalidade ou tricotomia).

É possível que que ocorra que tanto a ≤ b quanto b ≤ a; neste caso, tanto um quanto outro podem vir em primeiro lugar na lista de ordenação. Em uma ordenação estável, a ordem de entrada determina a ordem de classificação neste caso^[1].

Uma metáfora para pensar sobre o tipo de comparação é que alguém tenha um conjunto de pesos não rotulados e uma balança com escala. Seu objetivo é alinhar os pesos em ordem de seu peso, sem qualquer informação, exceto a obtida colocando-se dois pesos na balança e vendo qual deles é mais pesado (ou se ambos tem o mesmo peso).

Exemplos

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

Alguns exemplos de algoritmos de ordenação que não são algoritmos de comparação são:

Radix sort (examina os bits individuais das chaves)
Counting sort (indexa usando os valores das chaves)
Bucket sort (examina os bits das chaves)

Os limites de performance e as vantagens das diferentes técnicas de ordenação

Há limites fundamentais sobre o desempenho dos algoritmos de comparação. Um algoritmo de comparação deve ter um limite inferior de Ω(n log n) operações de comparação^[2]. Esta é uma consequência da escassa informação disponível, através de comparações sozinhas - ou, dito de outra forma, da vaga estrutura algébrica dos conjuntos totalmente ordenados. Nesse sentido, merge sort, heapsort e introsort são assintoticamente ótimos em termos de número de comparações que devem realizar, embora esta métrica negligencie outras operações. As três ordenações que não são por comparação anteriores atingem O ( n) de desempenho por meio de outras operações de comparações, o que lhes permite contornar este limite inferior (assumindo que os elementos são de tamanho constante).

No entanto, ordenações por comparação oferecem a notável vantagem de que o controle sobre a função de comparação permite a triagem dos muitos tipos de dados diferentes e um bom controle sobre a forma como a lista é ordenada. Por exemplo, revertendo o resultado da função de comparação permite que a lista seja ordenada ao contrário; por exemplo, pode-se classificar uma lista de tuplas em ordem lexicográfica simplesmente criando uma função de comparação que compara cada parte na seqüência:

function comparaTupla((aEsquerdo, bEsquerdo, cEsquerdo), (aDireito, bDireito, cDireito))
    if aEsquerdo ≠ aDireito
        return compare(aEsquerdo, aDireito)
    else if bEsquerdo ≠ bDireito
        return compare(bEsquerdo, bDireito)
    else
        return compare(cEsquerdo, cDireito)

A notação Ternário balanceado permite que sejam feitas comparações em uma única etapa, cujo resultado será um dos três: "menor que", "maior que" ou "igual a".

Ordenações por comparação geralmente se adaptam mais facilmente à ordens complexas, tais como a ordem dos números de ponto flutuante. Além disso, uma vez que uma função de comparação está escrita, qualquer tipo de comparação pode ser usada sem qualquer modificação; Ordenações que não são por comparação não exigem, geralmente, versões especializadas para cada tipo de dados.

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

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

O número de comparações que o algoritmo de ordenação por comparação exige aumenta na proporção de $n\log(n)$ , onde $n$ é o número de elementos para classificar. Este limite é assintoticamente apertado:

Dada uma lista de números distintos (podemos assumir isso, porque esta é uma análise de pior caso), existem fatorial de n permutações exatamente um dos quais é a lista em ordem de classificação. O algoritmo de ordenação deve obter informações suficientes a partir de comparações para identificar as permutações corretas. Se o algoritmo sempre termina após no máximo f(n) passos, não se pode distinguir mais de 2^f(n) casos porque as chaves são distintas e cada comparação tem apenas dois resultados possíveis. Por isso,

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

, ou equivalentemente

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

Pela aproximação de Stirling, sabemos que $\log _{2}(n!)$ é $\Omega (n\log _{2}n)$ . isso proporciona a parte inferior do argumento.

Um limite superior idêntico decorre da existência de algoritmos que atinjam este limite, no pior caso.

O argumento acima fornece um absoluto, ao invés de apenas um limite inferior assintótico sobre o número de comparações, a saber $\lceil \log _{2}(n!)\rceil$ comparações. Este limite inferior é razoavelmente bom (pode ser abordado dentro de uma tolerância linear por um simples merge sort), mas é conhecido por ser inexato. Por exemplo, $\lceil \log _{2}(13!)\rceil =33$ , mas o número mínimo de comparações para ordenar 13 elementos foi provado ser 34^[3].

Determinar o número exato de comparações necessárias para ordenar um determinado número de entradas é um problema computacionalmente difícil até mesmo para pequenos n, e nenhuma fórmula simples para a solução é conhecida.

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, todas as comparações darão tanto a>b ou a<b, e
a entrada é uma permutação aleatória, escolhida de modo uniforme a partir do conjunto de todas as permutações possíveis de n elementos, é impossível determinar qual ordem de entrada terá menos de log₂(n!) comparações em média.

Isso pode ser mais facilmente visto usando conceitos da teoria da informação. A entropia de Shannon de tal permutação aleatória é de log₂(n!) bits. Uma vez que a comparação só pode dar dois resultados, a quantidade máxima de informação que fornece é 1 bit. Após k comparações a entropia remanescente da permutação, tendo em conta os resultados destas comparações, é de, pelo menos log₂(n!) - k bits em média. Para realizar a ordenação, a informação completa é necessária, logo para a entropia restante deve ser 0. Daqui se conclui que k deve ser pelo menos log₂(n!).

Note que este difere do argumento do pior caso do exemplo acima, na medida em que não permite arredondamento para o número inteiro mais próximo. Por exemplo, para n = 3, o limite inferior para o pior caso é 3, o limite inferior para o caso médio, como mostrado acima é de aproximadamente 2,58, enquanto o maior limite inferior para o caso médio é de 8/3, aproximadamente 2,67.

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

Referências

↑ Ziviani, Nivio (1993). Projeto de Algoritmos. Com implementações em Pascal e C. São Paulo: Pioneira. 69 páginas. CDD 005.1
↑ http://planetmath.org/encyclopedia/LowerBoundForSorting.html
↑ Marcin Peczarski: The Ford-Johnson algorithm is still unbeaten for less than 47 elements. Inf. Process. Lett. 101(3): 126-128 (2007) doi:10.1016/j.ipl.2006.09.001

Bibliografia

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.1: Minimum-Comparison Sorting, pp. 180–197.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.1: Lower bounds for sorting, pp. 165–168.

[1] Ziviani, Nivio (1993). Projeto de Algoritmos. Com implementações em Pascal e C. São Paulo: Pioneira. 69 páginas. CDD 005.1

[2] ttp://planetmath.org/encyclopedia/LowerBoundForSorting.html

[3] Marcin Peczarski: The Ford-Johnson algorithm is still unbeaten for less than 47 elements. Inf. Process. Lett. 101(3): 126-128 (2007) doi:10.1016/j.ipl.2006.09.001

[1]

[2]

[3]