Stability

Nesta lição, verificaremos a natureza estável do algoritmo bubble sort.

O que é estabilidade?

Um algoritmo de ordenação é dito estável se dois objetos com chaves iguais aparecem na mesma ordem na saída ordenada conforme aparecem no array de entrada a ser ordenado.

Por exemplo, se tivermos que ordenar o array- [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] , aqui temos dois 8s, denotados por 8₁ e 8₂. Após a ordenação, dois arrays possíveis podem ser obtidos- [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] e [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>] . Ambos os arrays estão ordenados, mas no segundo, a ordem dos dois 8s é diferente, enquanto no primeiro array, é a mesma do array de entrada.

Agora, vamos verificar isso para o algoritmo bubble sort.

Primeira Passagem: [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] -> [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>]

Segunda Passagem: [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>] -> [2,4,6,1,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Após todas as passagens, o resultado final será: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Tente notar que a ordem dos 8s é a mesma tanto no array de saída quanto no de entrada.

Portanto, o algoritmo Bubble sort é Estável!