Stability

Dans cette leçon, nous allons vérifier la nature stable de l'algorithme de tri à bulles.

Qu'est-ce que la stabilité ?

Un algorithme de tri est dit stable si deux objets ayant des clés égales apparaissent dans le même ordre dans la sortie triée que dans le tableau d'entrée à trier.

Par exemple, si nous devons trier le tableau - [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] , nous avons ici deux 8, notés 8₁ et 8₂. Après le tri, deux tableaux possibles peuvent être obtenus - [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] et [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>] . Ces deux tableaux sont triés, mais dans le second, l'ordre des deux 8 est différent, alors que dans le premier tableau, il est le même que dans le tableau d'entrée.

Maintenant, vérifions cela pour l'algorithme de tri à bulles.

Première passe : [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>]

Deuxième passe : [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>]

Après toutes les passes, le résultat final sera : [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Essayez de remarquer que l'ordre des 8 est le même dans les tableaux de sortie et d'entrée.

Par conséquent, l'algorithme de tri à bulles est stable !