Stability

En esta lección, comprobaremos la naturaleza estable del algoritmo de ordenamiento de burbuja (bubble sort).

¿Qué es la estabilidad?

Se dice que un algoritmo de ordenamiento es estable si dos objetos con claves iguales aparecen en el mismo orden en la salida ordenada que como aparecen en el arreglo de entrada a ordenar.

Por ejemplo, si tenemos que ordenar el arreglo- [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] , aquí tenemos dos 8, denotados por 8₁ y 8₂. Después de ordenar, se pueden obtener dos arreglos posibles- [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] y [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>] . Ambos arreglos están ordenados, pero en el segundo, el orden de los dos 8 es diferente, mientras que en el primer arreglo, es el mismo que en el arreglo de entrada.

Ahora, comprobemos esto para el algoritmo de ordenamiento de burbuja.

Primera pasada: [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 pasada: [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>]

Después de todas las pasadas, el resultado final será: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Intenta notar que el orden de los 8 es el mismo tanto en el arreglo de salida como en el de entrada.

¡Por lo tanto, el algoritmo de ordenamiento de burbuja es Estable!