Что такое стабильность в алгоритмах сортировки и почему это важно?

Мне очень любопытно, почему стабильность является или не важна в алгоритмах сортировки?

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

Задний план : «стабильный» алгоритм сортировки сохраняет элементы с одинаковым ключом сортировки в порядке. Предположим, у нас есть список из 5 букв:

peach
straw
apple
spork

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

apple
peach
straw
spork

В нестабильном алгоритме сортировки strawили sporkмогут быть взаимозаменяемыми, но в стабильном алгоритме они остаются в одинаковых относительных позициях (то есть, посколькуstraw появляются раньше sporkво входных данных, они также появляются раньше sporkв выходных данных).

Мы могли бы отсортировать список слов, используя этот алгоритм: стабильная сортировка по столбцу 5, затем 4, затем 3, затем 2, затем 1. В конце концов, он будет правильно отсортирован. Убедите себя в этом. (кстати, этот алгоритм называется радикальной сортировкой)

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

Вы не можете сложить нестабильные сортировки таким же образом.

Алгоритм стабильной сортировки - это алгоритм , который сортирует идентичные элементы в том же порядке, в котором они появляются на входе, тогда как нестабильная сортировка может не соответствовать случаю. - _{^{Я благодарю моего лектора по алгоритмам Дидема Гозупека за то, что он дал представление об алгоритмах}} .

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

• Сортировка вставок
• Сортировка слиянием
• Пузырьковая сортировка
• Тим Сорт
• Подсчет Сортировка
• Блок Сортировка
• Quadsort
• Сортировка библиотеки
• Шейкер Сортировка
• Сортировка гномов
• Нечетный-четный Сортировка

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

• Сортировка кучи
• Сортировка выбора
• Сортировка оболочки
• Быстрая сортировка
• Интросорт (при условии быстрой сортировки)
• Сортировка деревьев
• Цикл сортировки
• Плавная сортировка
• Турнирная сортировка (в зависимости от Hesapsort)

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

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

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

Если вам нужна стабильность, это сложнее. Стабильные алгоритмы имеют более высокую загрузку ЦП и / или памяти, чем нестабильные алгоритмы. Поэтому, когда у вас большой набор данных, вы должны выбирать между биением процессора или памяти. Если вы ограничены как процессором, так и памятью, у вас есть проблема. Хороший компромиссный устойчивый алгоритм - это сортировка двоичного дерева; статья в Википедии содержит патетически простую реализацию C ++ на основе STL.

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

Это зависит от того, что вы делаете.

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

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

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

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

Ссылки: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Я знаю , что есть много ответов на это, но мне этот ответ , по Роберту Харви , резюмировать его гораздо более четко:

Стабильная сортировка - это та, которая сохраняет исходный порядок входного набора, где алгоритм [unstable] не различает два или более элементов.

Источник

Если вы предполагаете, что сортируете только цифры, и только их значения идентифицируют / различают их (например, элементы с одинаковыми значениями идентичны), тогда проблема стабильности сортировки не имеет смысла.

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

Например, у вас есть список данных, который содержит затраты времени [T] всех игроков на очистку лабиринта с уровнем [L] в игре. Предположим, нам нужно оценить игроков по скорости очистки лабиринта. Однако применяется дополнительное правило: игроки, которые чистят лабиринт с более высоким уровнем, всегда имеют более высокий ранг, независимо от того, сколько времени стоит.

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

Однако, если стабильная сортировка возможна, тогда вы можете просто отсортировать весь список по [T] (сначала более быстрые игроки), а затем по [L]. В этом случае относительный порядок игроков (по времени) не будет изменен после группировки их по уровню лабиринта, который они убрали.

PS: конечно, подход к сортировке дважды - не лучшее решение конкретной проблемы, но для объяснения вопроса об афише этого должно быть достаточно.

Стабильная сортировка всегда будет возвращать одно и то же решение (перестановку) на одном входе.

Например, [2,1,2] будет отсортировано с использованием стабильной сортировки в качестве перестановки [2,1,3] (сначала это индекс 2, затем индекс 1, затем индекс 3 в отсортированном выводе). Это означает, что выходные данные всегда перетасовываются одинаково. Другой нестабильной, но все же правильной перестановкой является [2,3,1].

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

Алгоритм стабильной сортировки необходим детерминистически.

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

Аналогичным примером является классический Excel, который ограничивает сортировку до 3 столбцов одновременно. Чтобы отсортировать 6 столбцов, выполняется сортировка по 3 наименее значимым столбцам, а затем сортировка по 3 наиболее значимым столбцам.

Классическим примером стабильной сортировки по основанию является сортировщик карт, используемый для сортировки по полю из 10 числовых столбцов. Карты сортируются от наименее значимой цифры к самой значимой цифре. На каждом проходе колода карт читается и разделяется на 10 разных лотков в соответствии с цифрой в этом столбце. Затем 10 лотков карт помещаются обратно во входной лоток по порядку (сначала «0», потом «9»). Затем выполняется следующий проход следующего столбца, пока все столбцы не будут отсортированы. Фактические сортировщики карточек имеют более 10 ячеек, поскольку на карточке 12 зон, столбец может быть пустым, а лоток неверно прочитан. Для сортировки букв требуется 2 прохода на столбец, 1 проход для цифры, 2 проход для зоны 12 11.

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