Ordenação estável: diferenças entre revisões
| 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. |
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. |
||
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. |
||
==Exemplo== |
|||
Um exemplo de um algoritmo de ordenação estável é o ''[[Counting Sort]]'', que ordena um vector de valores inteiros (cujo valor máximo é conhecido) colocando cada valor na sua posição homónima num vector de comprimento igual ao valor máximo. Este algoritmo tem a particularidade de ser linear no tamanho do vector que será ordenado, já que prescinde de comparações entre valores. |
|||
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 instá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 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: |
|||
| ⚫ | |||
*[[Cocktail sort]] |
|||
*[[Insertion sort]] |
|||
*[[Merge sort]] |
|||
*[[Bucket sort]] |
|||
*[[Counting sort]] |
|||
===Algoritmos instáveis=== |
|||
Alguns algoritmos de ordenação instáveis: |
|||
| ⚫ | |||
*[[Heapsort]] |
|||
*[[Selection sort]] |
|||
*[[Shell sort]] |
|||
== {{Veja também}} == |
== {{Veja também}} == |
||
*[[Complexidade computacional]] |
|||
* [[Ordenação instável]] |
|||
| ⚫ | |||
| ⚫ | |||
{{mínimo}} |
{{mínimo}} |
||
Revisão das 22h23min de 20 de janeiro de 2009
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.
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 instá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 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 instáveis
Alguns algoritmos de ordenação instáveis:
