Ordenação estável: diferenças entre revisões
Correção de link. |
m ajustes usando script |
||
| Linha 1: | Linha 1: | ||
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. <ref>{{ |
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. <ref>{{citar livro|autor=GOODRICH, Michael T.; TAMASSIA, Roberto|título=Projeto de Algoritmos|subtítulo=Fundamentos, Análise e Exemplos da Internet|idioma=|edição=|local=Porto Alegre|editora=Bookman|ano=2002|páginas=246-247|volume=|isbn= 85-363-0303-4}}</ref> |
||
Esta propriedade é útil apenas quando há dados associados às chaves de ordenação. |
Esta propriedade é útil apenas quando há dados associados às chaves de ordenação. |
||
| Linha 7: | Linha 7: | ||
Por exemplo, um algoritmo estável ordenando a sequência de números (chaves) com letras associadas (registros): |
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] |
3[a], 2[b], 2[c], 1[d] |
||
obrigatoriamente retornará: |
obrigatoriamente retornará: |
||
| Linha 30: | Linha 30: | ||
*[[Merge sort]] |
*[[Merge sort]] |
||
*[[Bucket sort]] |
*[[Bucket sort]] |
||
*[[Counting Sort]]<ref>{{ |
*[[Counting Sort]]<ref>{{citar livro|autor=CORMEN, Thomas H.; et al.|título=Algoritimos|subtítulo=Teoria e Prática|edição=2ª|local=Rio de Janeiro|editora=Campus|ano=2002|páginas=137|volume=|isbn= 85-352-0926-3}}</ref> |
||
===Algoritmos não estáveis=== |
===Algoritmos não estáveis=== |
||
| Linha 44: | Linha 44: | ||
{{Referências}} |
{{Referências}} |
||
== |
== Ver também == |
||
*[[Complexidade computacional]] |
*[[Complexidade computacional]] |
||
Revisão das 04h24min de 8 de abril de 2017
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
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
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
Alguns algoritmos de ordenação estáveis:
Algoritmos não estáveis
Alguns algoritmos de ordenação não estável:
- Selection Sort (Depende do algorítmo)
- Quicksort
- Heap Sort
- Shellsort
Referências
- ↑ 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
- ↑ 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
