Почему "неустойчивый сорт" считается плохим

Ответ 1

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

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

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

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

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

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