Stability

В этом уроке мы проверим стабильность алгоритма пузырьковой сортировки.

Что такое стабильность?

Алгоритм сортировки называется стабильным, если два объекта с одинаковыми ключами появляются в отсортированном выводе в том же порядке, в котором они были в исходном массиве.

Например, если нам нужно отсортировать массив — [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1], здесь у нас есть две восьмерки, обозначенные как 8₁ и 8₂. После сортировки можно получить два возможных массива — [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] и [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>]. Оба этих массива отсортированы, но во втором порядок двух восьмерок изменился, тогда как в первом массиве он такой же, как в исходном.

Теперь давайте проверим это для алгоритма пузырьковой сортировки.

Первый проход: [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>]

Второй проход: [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>]

После всех проходов окончательный результат будет: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

Обратите внимание, что порядок восьмерок одинаков как в исходном, так и в конечном массивах.

Следовательно, алгоритм пузырьковой сортировки является стабильным!