что такое устойчивая сортировка

Устойчивая сортировка

Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи.

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

Содержание

Пример

При сортировке записей вида (фамилия, имя, отчество) по фамилии значения ключей для Иванов Сергей и Иванов Иван будут одинаковы, поэтому устойчивая сортировка не переставит Сергея и Ивана местами (Python 3, сортировка timsort [1] ):

В результате записи будут отсортированы только по фамилии, с сохранением исходного порядка среди записей с одинаковыми фамилиями:

Алгоритмы устойчивой сортировки

Ниже приводятся описания алгоритмов устойчивой сортировки с временем работы не хуже O(n log 2 n) (кроме наихудших случаев в алгоритме с использованием устойчивого разделения). Во всех псевдокодах пара косых // означает комментарий до конца строки как в языке C++.

Сортировка слиянием с дополнительной памятью

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

Сортировка с использованием устойчивого разделения

Данный алгоритм похож на алгоритм быстрой сортировки. Так же как и в алгоритме быстрой сортировки, в данном алгоритме исходный массив разделяется на две части — в одной все элементы меньше или равны некоторому опорному элементу, а в другой — больше или равны. После этого разделённые части массива рекурсивно сортируются таким же образом. Отличие этого алгоритма от алгоритма быстрой сортировки в том, что здесь используется устойчивое разделение вместо неустойчивого. Ниже приведена реализация данного алгоритма на псевдокоде:

Для устойчивого разделения массива требуется O(n log n) элементарных операций. Так как «глубина» осуществляемого рекурсивного спуска в среднем случае составляет O(log n) то общая сложность алгоритма составляет O(n log² n). При этом алгоритму для осуществления рекурсии потребуется O(log n) стековой памяти, хотя в худшем случае общая сложность равна O(n² log n) и требуется O(n) памяти.

Алгоритмы сортировки слиянием без дополнительной памяти

Все описанные ниже алгоритмы основаны на слиянии уже отсортированных массивов без использования дополнительной памяти сверх O(log² n) стековой памяти (это — т. н. условие минимальной памяти [2] ) и отличаются лишь алгоритмом слияния. Далее приведен псевдокод алгоритмов (алгоритмы слияния — процедура Merge — приводятся отдельно для каждого метода):

Алгоритм Пратта

В алгоритме Пратта в отсортированных массивах находят два элемента α и β, которые являются медианами массива, состоящего из элементов обоих массивов. Тогда весь массив можно представить в виде aαbxβy. После этого осуществляется циклический сдвиг элементов в результате чего получаем такую последовательность: axβαby. Далее алгоритм слияния рекурсивно повторятся для массивов ax и by.

Циклический сдвиг элементов требует O(n) элементарных операций и O(1) дополнительной памяти, а поиск медиан в двух уже отсортированных массивах — O(log² n) элементарных операций и O(1) дополнительной памяти. Так как осуществляется O(log n) шагов рекурсии, то сложность такого алгоритма слияния составляет O(n log n), а общая сложность алгоритма сортировки — O(n log² n). При этом алгоритму потребуется O(log² n) стековой памяти.

Алгоритм без поиска медиан

От поиска медиан в предыдущем алгоритме можно избавиться следующим образом. В большем из двух массивов выбираем средний элемент α (опорный элемент). Далее в меньшем массиве находим позицию первого вхождения элемента большего или равного α. Назовем его β. После этого осуществляется циклический сдвиг элементов так же как и в алгоритме Пратта (aαbxβy → axβαby) и осуществляется рекурсивное слияние полученных частей. Псевдокод алгоритма слияния приведен ниже.

Процедуры FindFirstPosition и FindLastPosition практически совпадают с процедурой двоичного поиска:

В отличие от алгоритма Пратта в данном алгоритме разбиение может быть существенно неравным. Но даже в худшем случае алгоритм разобьёт весь диапазон [a..y] в соотношении 3:1 (если все элементы второго диапазона будут больше или меньше опорного и при этом оба диапазона имеют равное число элементов). Это гарантирует логарифмическое число шагов рекурсии при слиянии любых массивов. Таким образом получаем, что так же, как и в алгоритме Пратта, сложность алгоритма слияния равна O(n log n), сложность алгоритма сортировки — O(n log² n), а требуемая память — O(log² n).

Источник

Быстрая, экономная, устойчивая…

На вопрос, можно ли добиться выполнения одновременно всех трёх условий, большинство скажет «вряд ли». Википедия о таких алгоритмах не знает. Среди программистов ходят слухи, что вроде бы, что-то такое существует. Некоторые говорят, что есть «устойчивая быстрая сортировка» — но у той реализации, которую я видел, сложность была всё те же O(N*(log(N) 2 ) (по таймеру). И только в одном обсуждении на StackOverflow дали ссылку на статью B-C. Huang и M. A. Langston, Fast Stable Merging and Sorting in Constant Extra Space (1989-1992), в которой описан алгоритм со всеми тремя свойствами.

Авторы говорят, что их алгоритм не первый, и ссылаются на работу L. Trabb Pardo, Stable sorting and merging with optimal space and time bounds 1974 года. Это около 80 страниц отсканированного текста, и разобраться в нём я не пытался.

Сразу скажу для тех, кто попробует разобраться в статье Huang и Langston, что реализовать алгоритм в том виде, в каком он там описан, мне не удалось. Приём, который они используют в пункте 4.3, не работает, потому что утверждение «That is, it directly follows that the head of the rightmost block of a second-sublist series will temporarily have a key strictly greater than that of the record to its immediate right» верно не всегда. К счастью, в некоторых более поздних работах удалось найти способ, позволяющий обойти эту неприятность, и теперь я могу сказать, что алгоритм, удовлетворяющий всем трём условиям, действительно существует.

Основные операции

Ищем буфер для обмена.

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

Два состояния массива будем называть эквивалентными, если элементы с одинаковыми ключами в них находятся в одинаковом порядке. Главная проблема устойчивых in-place сортировок — не потерять эту эквивалентность, или всегда уметь её восстановить.

Пусть длина массива равна N. Если N 2 обменов. Поскольку NKeys у нас порядка 2*sqrt(N), то пока мы за границу не вышли.

Теперь у нас есть два варианта. Либо мы нашли заказанные K+S ключей, либо не нашли. Эти случаи обрабатываются слегка по-разному. Кроме того, есть случай, когда число различных ключей меньше 4 — для него тоже есть своя обработка.

Случай A. Различных ключей много.

У нас есть K+S различных ключей, собранных в начале массива. Первые K из них мы объявим «ключами для маркировки фрагментов» и пока трогать не будем. Остальные S будут буфером для слияния. Все оставшиеся элементы исходного массива — «данными», сейчас они лежат в конце массива.

A.1. Этап классической сортировки слиянием.

Напишем ещё две функции. Одна будет называться MergeLeft, другая MergeRight. Им подаются на вход фрагменты массивов, состоящие из трёх частей. В случае MergeLeft это буфер длины P, отсортированный фрагмент длины Q и отсортированный фрагмент длины R, где S≥R. Функция должна слить второй и третий фрагменты, положить результат в начало, а элементы буфера в произвольном порядке в конец данного фрагмента. Функция MergeRight работает зеркально — на входе у неё два отсортированных фрагмента, а за ними буфер, а на выходе — наоборот, буфер, а за ним отсортированный фрагмент. Выглядит это примерно так:

Сложность обеих функций не превосходит Q+R — как по сравнениям, так и по обменам.
Пользуясь функцией MergeLeft, мы можем отсортировать данные сначала по парам, потом по четвёркам,… вплоть до фрагментов длины S (напомню, что S — степень двойки). Каждый раз при сортировке M элементов мы используем кусочек буфера длины M/2, который в результате уезжает в правую часть массива. На этапе сортировки пар мы воспользуемся кусочком буфера длины 2, так что в итоге к моменту, когда отсортированные куски будут длины S, массив данных у нас окажется прижатым влево, а S элементов буфера будут справа. Теперь мы можем использовать MergeRight, отсортировать фрагменты длиной 2*S, и заодно, вернуть буфер в начало.

A.2. Этап блочной сортировки.

Сейчас у нас отсортированы фрагменты длиной G=2*S. Мы будем сливать их попарно, потом ещё раз попарно и т.д., пока не достигнем размера всего массива данных. Для этого у нас есть буфер длиной S и массив с ключами длиной K, где K ≤ L/S (L — полная длина массива данных).
Итак, цикл «пока G ≤ L».

Мы хотим слить два подряд идущих фрагмента длины G, причём непосредственно перед ними находится буфер длины S (G и S — степени двойки). Делим наши фрагменты на блоки длины S. Пусть их получилось K₁. Второй фрагмент в самом конце массива мог иметь длину меньше G, и после деления от него может остаться неполный блок, его мы тоже посчитаем (хотя двигать не будем). Возьмём первые K₁ ключей (они лежат в начале исходного массива), отсортируем их (например, вставками) и запомним индекс ключа с номером G/S (сейчас он равен G/S, но потом будет меняться) — назовём его midkey. Каждому ключу соответствует свой блок. Мы их используем, во-первых, чтобы различить первый и второй сливаемые фрагменты, а во-вторых, чтобы поддержать порядок блоков с одинаковыми элементами. Потому что сейчас мы их будем перемешивать как попало.

Отсортируем блоки. Порядок будет определяться первыми элементами, а если они равны — то соответствующими этим блокам ключами. Единственная сортировка, которой мы можем здесь воспользоваться — это сортировка выбором минимального элемента, поскольку она требует не более K₁ обмена (и K₁ 2 /2 сравнений): обмен двух блоков это дорогая процедура, но, поскольку S это примерно sqrt(N), то весь этап сортировки укладывается в O(N) операций. Когда мы переставляем два блока, то переставим и соответствующие им ключи, не забывая следить за ключом midkey. Неполный блок (если он есть) при этой сортировке мы не трогаем!

Блоки, ранее принадлежавшие первому фрагменту, мы будем обозначать буквой A, а блоки, принадлежавшие второму — буквой B. При нашей сортировке порядок блоков, соответствовавших каждому фрагменту,
сохранился.

Неполный блок всегда принадлежит фрагменту B. Просмотрим блоки, идущие перед ним, чтобы узнать, перед каким блоком его следовало бы вставить. Возможно, что его придётся вставить в самое начало, или оставить на месте — в алгоритме на эти случаи нужно обратить особое внимание. На следующем этапе трогать блоки, которые следовало бы подвинуть (все они из фрагмента A), мы пока не будем.

Чтобы обработать очередной блок, нам придётся написать ещё одну функцию SmartMergeLeft (и она не последняя!). На вход ей, как и MergeLeft, подаются буфер и два фрагмента, причём порядок этих фрагментов может быть неправильным (тогда при слиянии надо будет в случае равных элементов брать элемент из второго фрагмента). Функция должна переставлять элементы в начало только до тех пор, пока оба фрагмента непусты. Как только один из них кончится, она должна перенести оставшиеся элементы другого фрагмента в конец (если второй фрагмент кончился раньше), сообщить их число, и то, в каком фрагменте они были.
Примерно так:

В первом случае сначала кончились элементы из B, и в конце остались последние элементы из A, а во втором — наоборот.
Пользуясь этой функцией, мы легко можем продвинуться на один блок. Если тип следующего блока такой же, как у последних необработанных элементов, мы меняем их с буфером, и говорим, что T=0, а необработанным является новый блок (ситуация такая же, как в начале). Если типы разные, вызываем SmartMergeLeft, и она всё делает сама — элементы, которые останутся в конце блока, и будут необработанными.

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

Либо последние оставшиеся необработанные элементы — из фрагмента B. Тогда последний из этих элементов меньше, чем первый элемент из следующего за ним блока A (если такой есть), и мы можем смело обменять необработанные элементы с буфером.

Либо эти элементы из фрагмента A. Тогда мы просто виртуально приклеиваем их к следующим за ними блокам (опять же, если они есть).
В обоих случаях получаем одну и ту же ситуацию — буфер, за ним элементы из фрагмента A, потом — не более, чем S элементов из фрагмента B. Готовая ситуация для функции MergeLeft. Вызываем её — и фрагменты слиты, причём буфер оказался после них.

Проходим этой процедурой по всем парам фрагментов длины G, пока не дойдём до конца массива данных. После чего сдвигаем все данные вправо на S элементов (возвращая буфер в начало), и удваиваем значение S.
Конец цикла.

A.3. Завершение.

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

Функция MergeWithoutBuffer получает на вход два отсортированных фрагмента длины P и Q. Предположим, что P 1/3 (напомним, что M — число различных ключей в массиве). Размером блока у нас будет S=2*G/K₁.

Сортируем ключи и блоки так же, как в A.2. Для этого буфера не нужно.
Теперь нам нужно пройтись по массиву и слить блоки. Напишем функцию SmartMergeWithoutBuffer, являющуюся гибридом MergeWithoutBuffer и SmartMergeLeft. В ней предполагается, что первый фрагмент короче второго. Она работает так же, как MergeWithoutBuffer, но учитывает, что порядок фрагментов мог быть неправильным, а кроме того, сообщает, сколько элементов и из какого фрагмента остались в конце массива. Вызывая эту функцию вместо SmartMergeLeft, а функцию MergeWithoutBuffer — вместо MergeLeft в конце, получим слитые фрагменты.

Казалось бы, здесь мы и проиграли — максимальная длина блока в худшем случае (K=4,G=N/2) равна N/4, а значит, функции SmartMergeWithoutBuffer может потребоваться O(N^2) операций. Но нас спасает то, что число различных ключей в массиве мало — и можно показать, что сложность SmartMergeWithoutBuffer не превосходит P*m+Q, где m — число различных ключей в первом фрагменте. А поскольку сумма числа различных ключей по всем K/2 блокам фрагмента длины G (сделайте глубокий вдох и перечитайте — проще я сформулировать не могу) не превосходит K/2+M, то на слияние двух фрагментов длины G потратится не более O(G) операций.

B.3. Завершение.

Этот этап не отличается от A.3.

Случай C. Различных ключей не больше трёх.

Здесь мы пишем обычную сортировку слиянием (без рекурсии — сортируем по 2, потом по 4 элемента и т.д.), а для слияния фрагментов используем MergeWithoutBuffers. Поскольку различных ключей в массиве мало, её сложность будет линейной от длины сливаемых фрагментов, а значит, общая сложность — O(N*log(N)).

Реализация и выводы.

Реализация получилась громоздкой — почти 400 строк на C++ (фактически, он написан на C — надо только перенести описания переменных в начало функций). Скорость работы сильно различается для случаев A и B. Хуже всего ситуация, когда различных ключей много, но чуть-чуть меньше, чем нужно для перехода к случаю A — в этой ситуации алгоритм работает медленнее, чем в случае A, примерно в 3 раза. Тем не менее, оценка сложности N*log(N) сохраняется.

На больших массивах (примерно от 10 миллионов) алгоритм почти всегда (кроме случаев совсем уж маленького числа различных ключей) обыгрывает InPlaceStableSort (тот, который за O(N*log(N) 2 )). Но тягаться с std::stable_sort он не в силах: хоть немного памяти найдётся всегда, а в этом случае std::stable_sort быстро переключается на обычный MergeSort, и легко и непринуждённо обгоняет всех, включая quicksort :). Так что реализованный алгоритм имеет лишь теоретическое значение.

Но всё-таки, он существует 🙂

UPDATE: Этап B2 можно сильно ускорить. Пока число G достаточно мало, может случиться так, что (K/2)^2>=2*G. В этом случае мы можем разделить множество ключей пополам, и половину использовать в качестве буфера обмена (а вторую половину — как ключи), и сливать фрагменты с помощью более быстрого метода из A2. А на обмены без буфера перейти в самом конце, когда G приблизится к размеру массива.
Чем больше у нас разных ключей, тем дольше работает слияние без буфера, но и тем дольше мы можем обойтись без него.
Эксперименты показывают, что в самом неблагоприятном случае алгоритму требуется не больше, чем 1.61*N*log₂N сравнений и 2.12*N*log₂N обменов (при N≤1000000, на случайных данных с заранее заданным числом различных ключей).

Источник

Алгоритм сортировки

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

Содержание

Формулировка задачи

,

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

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

[3]

В результате работы алгоритма и применения перестановки получается отсортированный массив:

Аналогично можно определить сортировку по невозрастанию.

Оценка алгоритма сортировки

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

Свойства и классификация

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

Также алгоритмы классифицируются по:

Список алгоритмов сортировки

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник