Ordenação estável

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

Um algoritmo de ordenação diz-se estável se preserva a ordem de registros de chaves iguais. Isto é, se tais registros aparecem na sequência ordenada na mesma ordem em que estão na sequência inicial. [1]

Esta propriedade é útil apenas quando há dados associados às chaves de ordenação.

Exemplo[editar | editar código-fonte]

Por exemplo, um algoritmo estável ordenando a sequência de números (chaves) com letras associadas (registros):

3[a], 2[b], 2[c], 1[d]

obrigatoriamente retornará:

1[d], 2[b], 2[c], 3[a]

enquanto algoritmos não estáveis sujeitam os elementos associados aos objetos a serem ordenados a mudanças:

1[d], 2[c], 2[b], 3[a]

Implementação[editar | editar código-fonte]

Certos algoritmos são estáveis a partir de sua concepção original, como o Counting sort ou o Merge sort. Porém. é possível implementar estabilidade artificialmente em certos algoritmos. Por exemplo, numa comparação de dois objetos de mesmo valor pode aplicar-se uma comparação adicional para verificar se a ordem original dos registros associados foi mantida. Neste caso, a implementação de estabilidade requer um custo adicional de eficiência.

Algoritmos estáveis[editar | editar código-fonte]

Alguns algoritmos de ordenação estáveis:

Algoritmos não estáveis[editar | editar código-fonte]

Alguns algoritmos de ordenação não estável:


Referências

  1. GOODRICH, Michael T.; TAMASSIA, Roberto (2002). Projeto de Algoritmos. Fundamentos, Análise e Exemplos da Internet. Porto Alegre: Bookman. pp. 246–247. ISBN 85-363-0303-4 
  2. CORMEN, Thomas H.; et al. (2002). Algoritimos. Teoria e Prática 2ª ed. Rio de Janeiro: Campus. 137 páginas. ISBN 85-352-0926-3 

Ver também[editar | editar código-fonte]

Wiki letter w.svg Este artigo é um esboço. Você pode ajudar a Wikipédia expandindo-o. Editor: considere marcar com um esboço mais específico.