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

Question

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

Answer 1

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

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

Например:

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

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

Answer 2

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

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

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

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

Answer 3

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

1. (1, "боб")
2. (3, «счет»)
3. (1, "Джейн")

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

1. (1, «Джейн»)
2. (1, «боб»)
3. (3, «счет»)

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

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

Answer 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

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

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

Answer 5

Пример:

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

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

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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

Answer 9

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

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

Answer 10

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

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

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

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

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

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

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

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

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