Почему Selection Sort не стабилен?

Это может быть тривиально, но я не понимаю, почему стандартная реализация Selection Sort нестабильна?

На каждой итерации вы найдете минимальный элемент в оставшемся массиве. Найдя этот минимум, вы можете выбрать первый минимум, который вы найдете, и обновлять его только тогда, когда элемент на самом деле меньше его. Таким образом, выбранный элемент на каждой итерации является первым минимумом, то есть первым в предыдущем порядке сортировки. Итак, по моему мнению, текущий сорт не уничтожит порядок, созданный предыдущим типом, на равных элементах.

Что мне не хватает?

Ответ 1

Небольшой пример:

Пусть b = B в

<B> , <b> , <a> , <C> (с < b < c)

После одного цикла последовательность сортируется, но порядок B и b изменился:

Но вы можете, однако, внедрить Selections Sort stable, если вместо переключения ввести минимальное значение. Но для того, чтобы быть эффективными, у вас должна быть структура данных, поддерживающая вставку с низкой стоимостью или в противном случае вы получите квадратичную сложность.

Ответ 2

Проблема заключается в том, что сортировка сортировки сводит элементы из передней части массива в пятно, освобожденное минимальным элементом, что может испортить отсортированный порядок. Например, предположим, что я сортирую

(4, 0), (4, 1), (1, 0)

Сортировка сортировки сначала сворачивает (1, 0) вперед:

(1, 0), (4, 1), (4, 0)

И теперь (4, 0) и (4, 1) не соответствуют порядку, с которого они начали в сортировке. Выполнение этого до завершения оставляет элементы в этом порядке, а 4s выходят из строя.

Надеюсь, это поможет!

Ответ 3

Стабильные средства не вычисляются дальше, если элементы уже отсортированы, но вычисляются до конца, следовательно, они нестабильны.