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

Question

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

Answer 1

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

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

peach
straw
apple
spork

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

apple
peach
straw
spork

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

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

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

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

Answer 2

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

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

• Сортировка вставок
• Сортировка слиянием
• Bubble Sort
• Тим Сорт
• Подсчет сортировки

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

• Сортировка кучи
• Выбор сортировки
• Оболочка сортировки
• Быстрая сортировка

Answer 3

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

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

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

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

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

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

Answer 7

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

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

Источник

Answer 8

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

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

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

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

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

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

Answer 9

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

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

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

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