Stabilność

W tej lekcji sprawdzimy, czy algorytm sortowania bąbelkowego jest stabilny.

Czym jest stabilność?

Algorytm sortowania jest stabilny, jeśli dwa obiekty o równych kluczach pojawiają się w posortowanym wyniku w tej samej kolejności, w jakiej występują w wejściowej tablicy przeznaczonej do sortowania.

Na przykład, jeśli mamy posortować tablicę — [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] — mamy tu dwie ósemki, oznaczone jako 8₁ i 8₂. Po sortowaniu możemy otrzymać dwie możliwe tablice — [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] oraz [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>]. Obie te tablice są posortowane, ale w drugiej kolejność dwóch ósemek jest inna, natomiast w pierwszej tablicy jest taka sama jak w tablicy wejściowej.

Sprawdźmy teraz, jak jest w przypadku algorytmu sortowania bąbelkowego.

Pierwsze przejście: [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>]

Drugie przejście: [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>]

Po wszystkich przejściach końcowym wynikiem będzie: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Zwróć uwagę, że kolejność ósemek jest taka sama w tablicy wynikowej i wejściowej.

Zatem algorytm sortowania bąbelkowego jest stabilny!