Abrir menu principal

Alterações

744 bytes adicionados ,  22h23min de 20 de janeiro de 2009
sem resumo de edição
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==
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:
 
* [[Bubble sort]]
*[[Cocktail sort]]
*[[Insertion sort]]
*[[Merge sort]]
*[[Bucket sort]]
*[[Counting sort]]
 
===Algoritmos instáveis===
 
Alguns algoritmos de ordenação instáveis:
 
* [[Quicksort]]
*[[Heapsort]]
*[[Selection sort]]
*[[Shell sort]]
 
== {{Veja também}} ==
 
*[[Complexidade computacional]]
* [[Ordenação instável]]
* [[Quicksort]]
* [[Bubble sort]]
 
{{mínimo}}
400

edições