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

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

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

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

Неустойчивая Сортировка Алгоритмы:

• Куча Вроде
• сортировка выбор
• Shell sort
• Быстрая Сортировка

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

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

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

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

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

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

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

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

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

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

ссылки: http://www.math.uic.edu/~leon / cs-mcs401-s08 / раздаточные материалы / stability. pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

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

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

источник

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

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

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

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

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

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

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

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

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

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