Ordenação estável

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. 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:

• Selection Sort
• Quick Sort
• Heap Sort
• Shell Sort
• Counting Sort

Ver também

• Complexidade computacional