Почему выбор Сортировка нестабильна?

Question

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

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

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

Answer 1

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

Пусть B = B в

< B>, < б>, < а>, < C> (с < б < с)

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

< a>, < b>, < B >, < c>

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

Answer 2

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

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

сорт первый обменивает (1, 0) на фронт:

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

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

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

Answer 3

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