В чем преимущество стабилизации алгоритма сортировки?

Ответ 1

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

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

Например:

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

Гарантируется, что он будет в правильном порядке.

Ответ 2

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

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

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

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

Ответ 3

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

• (1, "bob" )
• (3, "bill" )
• (1, "jane" )

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

• (1, "jane" )
• (1, "bob" )
• (3, "bill" )

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

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

Ответ 4

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

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

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

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

Ответ 5

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

Ответ 6

Пример:

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

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

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

Устойчивый алгоритм гарантирует, что право на 2 сотрудника на номер телефона получит бонус.

Ответ 7

Один случай - это сортировка по нескольким клавишам. Например, чтобы отсортировать список пар имени/фамилии, вы можете отсортировать сначала по первому имени, а затем по фамилии.

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

Ответ 8

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

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

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

Ответ 9

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

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

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

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

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

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

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

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

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

Ответ 10

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

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