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

Question

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

Answer 1

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

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

peach
straw
apple
spork

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

apple
peach
straw
spork

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

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

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

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

Answer 2

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

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

• Сортировка по вставке
• Сортировка слиянием
• Пузырьковая Сортировка
• Сортировка по Времени
• Счетная Сортировка

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

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

Answer 3

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

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

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

Ссылки:http://www.math.uic.edu /~leon/cs-mcs401-s08/раздаточные материалы/стабильность.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].

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

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