Почему нестабильная сортировка считается плохой

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

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

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

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

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

Потому что они могут работать лучше, чем я... от разработчика Слияние:

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

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

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