Каково преимущество для алгоритма сортировки, чтобы быть стабильным?

Это позволяет вашему сорту «цепляться» через множество условий.

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

Например:

• Смит, Альфред
• Смит, Зед

Будет гарантированно быть в правильном порядке.

Пример:

Скажем, у вас есть структура данных, которая содержит пары телефонных номеров и сотрудников, которые их вызвали. Номер / запись сотрудника добавляется после каждого звонка. Некоторые телефонные номера могут вызываться несколькими разными сотрудниками.

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

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

Стабильный алгоритм гарантирует, что на каждого телефонного номера нужно 2 подходящих сотрудника. получить бонус.

Алгоритм сортировки стабилен, если он сохраняет порядок повторяющихся ключей.

Хорошо, хорошо, но почему это должно быть важно? Что ж, вопрос «стабильности» в алгоритме сортировки возникает, когда мы хотим отсортировать одни и те же данные более одного раза по разным ключам.

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

Из Алгоритмы стабильной сортировки

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

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

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

Самое большое преимущество приходит, когда исходный ордер имеет какое-то значение сам по себе. Я не смог придумать хороший пример, но я вижу, что Джефф Х сделал это, когда я думал об этом.

Один случай, когда вы хотите отсортировать по нескольким ключам. Например, чтобы отсортировать список пар «имя / фамилия», вы могли бы отсортировать сначала по имени, а затем по фамилии.

Если бы ваша сортировка была нестабильной, вы потеряли бы преимущество первой сортировки.

Допустим, вы сортируете на входе набор, который имеет два поля, и вы сортируете только по первому. '|' символ разделяет поля.

Во входном наборе у вас много записей, но у вас есть 3 записи, которые выглядят как

. , , AAA | буксировка , , , AAA | прокат автомобилей , , , AAA | сантехнические , ,

Теперь, когда вы закончите сортировку, вы ожидаете, что все поля с AAA в них будут вместе.

Стабильная сортировка даст вам: , , , AAA | буксировка AAA | прокат автомобилей AAA | сантехнические , ,

т. Е. Три записи, имеющие один и тот же ключ сортировки, AAA, находятся в том же порядке на выходе, что и на входе. Обратите внимание, что они не отсортированы по второму полю, потому что вы не сортировали по второму полю в записи.

Нестабильная сортировка даст вам: , , , AAA | сантехнические AAA | прокат автомобилей AAA | буксировка , ,

Обратите внимание, что записи по-прежнему сортируются только в первом поле, и порядок второе поле отличается от порядка ввода.

Нестабильная сортировка может быть быстрее. Стабильная сортировка имеет тенденцию имитировать то, что имеют в виду ученые-не математики / не математики, когда они что-то сортируют. Т.е., если бы вы делали вставку с индексными карточками, у вас, скорее всего, была бы стабильная сортировка.

Примером является очередь с приоритетами. Скажем, у вас есть это:

1. (1, «Боб»)
2. (3, «Билл»)
3. (1, «Джейн»)

Если вы сортируете это от наименьшего к наибольшему числу, нестабильный sort может сделать это.

1. (1, "jane")
2. (1, "bob")
3. (3, "bill")

... но тогда "jane" опередила " bob ", хотя это должно было быть наоборот.

Как правило, они полезны для сортировки нескольких записей за несколько шагов.

Не вся сортировка основана на полном значении. Рассмотрим список людей. Я могу отсортировать их только по именам, а не по всей их информации. Благодаря стабильному алгоритму сортировки я знаю, что если у меня есть два человека по имени «Джон Смит», их относительный порядок будет сохранен.

Last     First       Phone
-----------------------------
Wilson   Peter       555-1212
Smith    John        123-4567
Smith    John        012-3456
Adams    Gabriel     533-5574

Так как два «Джона Смита» уже «отсортированы» (они находятся в том порядке, в котором они мне нужны), я не хочу, чтобы они меняли позиции. Если я отсортирую эти элементы в последнюю очередь, а затем сначала с помощью нестабильного алгоритма сортировки, я могу получить либо следующее:

Last     First       Phone
-----------------------------
Adams    Gabriel     533-5574
Smith    John        123-4567
Smith    John        012-3456
Wilson   Peter       555-1212

Это то, что я хочу, либо я могу получить следующее:

Last     First       Phone
-----------------------------
Adams    Gabriel     533-5574
Smith    John        012-3456
Smith    John        123-4567
Wilson   Peter       555-1212

(Вы видите два " Джона Смита поменялись местами). Это НЕ то, что я хочу.

Если бы я использовал стабильный алгоритм сортировки, я бы гарантированно получил первый вариант, что мне и нужно.

Невозможно всегда сравнивать все поля сразу. Пара примеров: (1) ограничения памяти, когда вы сортируете большой дисковый файл, и в основной памяти нет места для всех полей всех записей; (2) Сортировка списка указателей базового класса, в котором некоторые объекты могут быть производными подклассами (у вас есть доступ только к полям базового класса).

Кроме того, стабильные сортировки имеют детерминированный вывод при том же вводе, который может быть важно для отладки и тестирования.