Stabilità

In questa lezione verificheremo la stabilità dell'algoritmo bubble sort.

Che cos'è la stabilità?

Un algoritmo di ordinamento è considerato stabile se due oggetti con chiavi uguali compaiono nello stesso ordine nell'output ordinato in cui compaiono nell'array di input da ordinare.

Ad esempio, se dobbiamo ordinare l'array- [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] , qui abbiamo due 8, indicati con 8₁ e 8₂. Dopo l'ordinamento, si possono ottenere due possibili array- [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>] . Entrambi gli array sono ordinati, ma nel secondo l'ordine dei due 8 è diverso, mentre nel primo array è lo stesso dell'array di input.

Ora verifichiamo questo per l'algoritmo bubble sort.

Primo passaggio: [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>]

Secondo passaggio: [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>]

Dopo tutti i passaggi, l'output finale sarà: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Nota che l'ordine degli 8 è lo stesso negli array di output e di input.

Quindi, l'algoritmo Bubble sort è stabile!