Рубрики

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

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

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

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

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

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

Пример, где это полезно
Рассмотрим следующий набор данных «Имена учеников» и соответствующие им разделы классов.

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

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

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

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

Какие алгоритмы сортировки стабильны?
Некоторые алгоритмы сортировки по своей природе стабильны, такие как Bubble Sort , Insertion Sort , Merge Sort , Count Sort и т. Д.
Стабильные сортировки на основе сравнения, такие как сортировка слиянием и сортировка вставкой, поддерживают стабильность, гарантируя, что
Элемент приходит раньше если и только если , здесь i, j индексы и ,
поскольку , относительный порядок сохраняется т.е. приходит раньше ,
Другие сортировки, не основанные на сравнении, такие как счетная сортировка, поддерживают стабильность, обеспечивая заполнение отсортированного массива в обратном порядке, чтобы элементы с эквивалентными ключами имели одинаковую относительную позицию.
Некоторые сортировки, такие как сортировка по Radix, зависят от другой сортировки, с единственным требованием, чтобы другая сортировка была стабильной.

Какие алгоритмы сортировки нестабильны?
Быстрая сортировка , сортировка кучи и т. Д. Может быть сделана стабильной, если принять во внимание положение элементов. Это изменение может быть сделано таким образом, чтобы не сильно снижать производительность и занимать дополнительное пространство, возможно, ,

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

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

Эта статья предоставлена Чирагом Манвани . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

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

0.00 (0%) 0 votes