Почему «нестабильный сорт» считается плохим

Question

Просто интересно, может ли кто-нибудь объяснить, почему «нестабильная сортировка» считается плохой? В принципе, я не вижу ситуаций, где это действительно имело бы значение. Может ли кто-нибудь позаботиться о предоставлении одного?

Answer 1

Если у вас есть графический интерфейс, который позволяет людям сортировать по отдельным столбцам, щелкая по этому столбцу, и вы используете стабильную сортировку, то люди, которые знают, могут получить многостолбцовую сортировку по столбцам A, B, C, нажав на столбцы C, B, A в таком порядке. Поскольку сортировка стабильна, при нажатии на B все записи с одинаковыми ключами в B все равно будут отсортированы по C, поэтому после нажатия на B записи сортируются по B, C. Аналогично, после нажатия на A записи сортируются по A, B, C.

(К сожалению, в прошлый раз, когда я пробовал это на каком-либо продукте Microsoft, похоже, что он не использовал стабильную сортировку, поэтому неудивительно, что этот трюк не более известен).

Answer 2

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

Answer 3

Есть только несколько случаев, когда вам нужен устойчивый алгоритм сортировки. Примером этого является то, что вы реализуете что-то вроде сортировки Radix, что зависит от идеи, что алгоритм сортировки сравнения, используемый в качестве строительного блока, стабилен. (Сортировка Radix может работать за линейное время, но ее входы более ограничены, чем алгоритмы сортировки сравнения. (Для сортировки сравнения требуется время O (n lg n)))

Не обязательно, что нестабильный сорт является "плохим"; более того, стабильный сорт «желателен в некоторых случаях». Вот почему языки программирования, например Стандартная библиотека шаблонов C ++, обеспечивает как - например, std::sort и std::stable_sort - которые позволяют вам указать, когда вам нужна стабильность, а когда нет.

Answer 4

Потому что они могут работать лучше, чем я ... from Developer Fusion :

Существует два вида алгоритмов сортировки: "стабильные сортировки" и "нестабильные сортировки"».Эти термины относятся к действию, которое выполняется, когда два значения сравниваются как равные.Если у вас есть массив T0..size с двумя элементами Tn и Tk для n

Обратите внимание, что алгоритмы сортировки, такие как быстрая сортировка, не являются стабильными или нестабильными.Реализация определит, какой это.

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