Gabarito Certo
algoritmos estáveis - MIB, homens de preto - merge, insert e bubble sort
algoritmos instáveis - SSH Q, segurança - select, shell, heap e quick sort
"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !
Um algoritmo de ordenação é estável (= stable) se não altera a posição relativa dos elementos que têm o mesmo valor. Digamos, por exemplo, que um vetor de números do tipo double é ordenado com base na parte inteira dos números, ignorando a parte fracionária. Se o algoritmo de ordenação for estável, os números que têm a mesma parte inteira continuarão na mesma ordem em que estavam originalmente. Na seguinte figura, a primeira linha mostra o vetor original e a segunda, o vetor ordenado:
44.0 55.1 55.2 66.0 22.9 11.022.5 33.0
11.0 22.9 22.5 33.0 44.0 55.1 55.2 66.0 Observe que 22.9 e 22.5 permaneceram na mesma ordem que estavam antes da ordenação, o mesmo para 55.1 e 55.2
Eis outro exemplo. Digamos que cada elemento do vetor é um struct com dois campos: o primeiro contém o nome de uma pessoa e o segundo contém o ano de nascimento da pessoa. Suponha que o vetor original tem dois João da Silva, primeiro o que nasceu em 1990 e depois o que nasceu em 1995. Se o vetor for ordenado por um algoritmo estável com base no primeiro campo, os dois João da Silva continuarão na mesma ordem relativa: primeiro o de 1990 e depois o de 1995.