Главная | Обратная связь | Поможем написать вашу работу!

Внутренняя сортировка

Задачу внутренней сортировки можно формально представить следующим образом: Для заданной последовательности ключей необходимо найти перестановку для которой выполняется условие

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

Нижние оценки. При построении эффективных алгоритмов необходимо понимать, к какой временной оценке его работы мы должны стремиться. Построение нижних оценок временной сложности является достаточно серьезной задачей и значения оценки может зависеть как от объема исходной информации, так и ограничений, налагаемых на вычислитель. Часто нижние оценки получаются из мощностных соображений (энтропийный подход), иногда при построении удается использовать структурные особенности задачи. В большинстве своем энтропийный подход дает неэффективные нижние оценки (устанавливается лишь факт существования объекта определенной сложности без конструктивного описания самого объекта)[17]. В этом случае бывает обычно трудно построить как объекты, которые имеют соответствующую сложность, так и алгоритмы описания таких объектов. Однако введение разумных ограничений и выделение соответствующих классов задач нередко позволяют находить нижние сложностные оценки с точностью до порядка роста соответствующих функций, участвующих в оценке.

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

Очевидно, тривиальной нижней оценкой для задачи сортировки размерности является линейная функция , поскольку каждый элемент исходной последовательности должен обрабатываться соответствующим алгоритмом. С другой стороны задачу сортировки можно рассматривать как задачу поиска подходящей последовательности во множестве всех перестановок. Известно, что всего имеется перестановок из элементов. Присвоим каждой перестановке номер в виде двоичного вектора некоторой длины так, чтобы разным перестановкам соответствовали разные вектора. Поскольку число двоичных векторов длины равно , то должно выполняться условие , из которой следует мощностная оценка , которая утверждает, что самое длинное описание перестановки в качестве двоичной последовательности будет . Возникает вопрос, как связаны двоичные вектора с последовательностью шагов алгоритма сортировки? Рассмотрим класс алгоритмов, которые в качестве базовых операций используют операции сравнения элементов и операции их перестановки. Тогда операция сравнения двух любых элементов и разбивает множество всех перестановок на два подмножества и . Каждое из полученных подмножеств[18] также можно разбить на части, используя другое сравнение. Аккуратная реализация этой идеи приводит к построению дерева решений, листьями которого являются различные порядки[19] следования элементов исходного множества, а внутренние вершины представляют результат решения, которое принимается после сравнения соответствующих элементов множества. Ниже приведен пример дерева решений для множества . В листьях дерева указан порядок сортировки в зависимости от принятых решений

В [2] доказано, что высота любого дерева решений, упорядочивающего последовательность из различных элементов не меньше . Из этого результата вытекает важное следствие:

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

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

Верхние оценки. Пожалуй, никакая другая проблема не породила такого количества разнообразнейших алгоритмов, как задача сортировки. Существует ли некий "универсальный", наилучший алгоритм? В определенном смысле, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом. Алгоритмы сортировки разбиваются на два класса:

1. Алгоритмы, которые используют только операции сравнения ключей и перестановки элементов;

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

Сначала исследуем алгоритмы первого класса. Временная сложность алгоритма складывается из числа сравнений и числа перестановок элементов исходного множества. Число сравнений в алгоритмах сортировки принято обозначать через , соответственно для числа обменов будем использовать символ [20]. При исследовании сложности обычно выделяют три случая: минимальную сложность алгоритма ( - обычно она достигается для уже отсортированной последовательности и в этом случае подсчитывается число шагов, необходимых для подтверждения факта отсортированности исходной последовательности), для худшего случая (, обычно, худший случай достигается на последовательности, отсортированной в обратном порядке) и среднее значение сложности (), взятое по всем возможным последовательностям на входе алгоритма при условии, что каждое из них встречается с одинаковой вероятностью.

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

Сортировка включениями
Сортировка выбором
Сортировка обменом
Сортировка слиянием

Различие между этими методами достаточно условное. Поскольку на каждом шаге алгоритм работает только с парой элементов, то каждый алгоритм в процессе своей работы должен формировать линейно упорядоченные подмножества, объединение которых на завершающей стадии работы алгоритма и дают необходимый результат. Первоначально исходная последовательность состоит из одиночных несвязанных между собой элементов. Каждое сравнение некоторых выбранных элементов с последующей возможной их перестановкой определяет подмножества из двух элементов, которые находятся в необходимом отношении. Рассматривая полученное подмножество как самостоятельный объект, и вводя специальные операции на таких объектах можно строить все более длинные последовательности. Большинство алгоритмов сортировки на каждом шаге разбивают текущую последовательность на две части: множество элементов, из которого извлекается информация об элементе или группе элементов, и множество элементов, которое по шагам формируется алгоритмом. Разбиение последовательности на части и может меняться в зависимости от этапа построения (иногда, значительно), и поэтому хорошие алгоритмы должны формулировать простые правила построения этого разбиения. Очень часто разбиение строится на единой структуре данных путем указания границ соответствующих частей с использованием указателей (плавающих границ). Алгоритм использует как источник данных, основной операцией на является задача поиска элемента (группы элементов), удовлетворяющего некоторому условию. является приёмником, который должен уметь дополнять себя элементами из с сохранением требуемого порядка элементов (для этого необходимо уметь решать задачу объединения множеств с сохранением имеющегося на них порядка). В процессе работы алгоритма и могут меняться местами, накапливая информацию о последовательности в целом. Поэтому с множеством можно связать операции поиска элемента (обычно минимального или максимального), удаления элемента и поверки пустоты множества. С связывается операции вставки. Но поскольку и реализуются как части одной структуры, то вообще говоря, в задаче сортировки мы имеем один абстрактный тип данных множество с операциями поиска, вставки, удаления и проверки пустоты.

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

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

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

		№ фазы
13, 11, 23, 10, 12, 18, 30, 8, 7, 6, 15, 21	пустое
13, 11, 23, 10, 12, 18, 30, 8, 7, 6, 15		После 1-ой
13, 11, 23, 10, 12, 18, 30, 8, 7, 6	15, 21	После 2-ой
13, 11, 23, 10, 12, 18, 30, 8, 7	6, 15, 21	После 3-ей
13, 11, 23, 10, 12, 18, 30, 8	6, 7, 15, 21	После 4-ой
13, 11, 23, 10, 12, 18, 30	6, 7, 8, 15, 21	После 5-ой
13, 11, 23, 10, 12, 18	6, 7, 8, 15, 21, 30	После 6-ой
13, 11, 23, 10, 12	6, 7, 8, 15, 18, 21, 30	После 7-ой
13, 11, 23, 10	6, 7, 8, 12,15, 18, 21, 30	После 8-ой
13, 11, 23	6, 7, 8, 10,12,15, 18, 21, 30	После 9-ой
13, 11	6, 7, 8, 10, 12, 15, 18, 21, 23, 30	После 10-ой
	6, 7, 8, 10, 11,12, 15, 18, 21, 23, 30	После 11-ой
пустая	6, 7, 8, 10, 11,12, 13,15, 18, 21, 23, 30	После 12-ой

Жирным шрифтом в выделены элементы, передаваемые в . В выделены элементы, которые участвуют в обменах при вставке.

Однако слияние одноэлементной последовательности с требует поиска места этого элемента в упорядоченной последовательности [21]. Время этого поиска с одной стороны зависит от числа элементов в , с другой стороны определяется структурой данных, использованной для представления . При последовательной структуре (массив, линейный список) число сравнений при включении элемента пропорционально числу элементов , что в общем случае дает квадратичную оценку сложности алгоритма. Ниже приведены оценки сложности работы алгоритма в этом случае[23]:

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

Улучшение алгоритма сортировки простым включением заключается в ускорении поиска места вставляемого элемента в . В самом деле, используя упорядоченность элементов, входящих в , и применяя двоичный поиск, можно значительно уменьшить число сравнений (до ). К сожалению, такая модификация при использовании массивов не уменьшает общее время работы алгоритма, поскольку не меняет числа пересылок. С другой стороны линейные списки также плохо подходят для данного метода сортировки, поскольку списочная структура предполагает реализацию последовательного поиска. Можно в качестве структуры данных для использовать древообразные структуры (метод Уиллера), которые реализуют вставки новых элементов при помощи указателей и позволяют получить общую оценку [14].

Простой обмен (пузырьковая сортировка): Обозначим через исходную последовательность элементов. Положим и . Алгоритм многократно проходит по элементам из , сравнивая соседние пары элементов и при необходимости переставляя их, если эти элементы не удовлетворяют требуемому отношению порядка. Результатом каждого такого прохода, в зависимости от вида сортировки является максимальный элемент, который извлекается из и добавляется в [22]. Добавление найденного элемента в , как и в методе простого выбора, требует константного (не зависящего от числа элементов в ) числа шагов. Процесс повторяется до тех пор, пока не станет пустым. Таким образом, алгоритм сводится к операциям: выбора из максимального элемента и включения найденного элемента в с сохранением отношения порядка. Выбор максимального элемента из совмещен с движением этого элемента по последовательности. Поэтому к моменту извлечения, этот элемент является крайним в , и операция выбора может быть реализована с изменением указателей на границы между и .

		№ фазы
13, 11, 23, 10, 12, 18, 30, 8, 7, 6, 15, 21 11, 13, 23, 10, 12, 18, 30, 8, 7, 6, 15, 21 11, 13, 10,23, 12, 18, 30, 8, 7, 6, 15, 21 11, 13, 10,12, 23, 18, 30, 8, 7, 6, 15, 21 11, 13, 10,12, 18,23,30, 8, 7, 6, 15, 21 11, 13, 10,12, 18,23,8,30, 7, 6, 15, 21 11, 13, 10,12, 18,23,8,7,30, 6, 15, 21 11, 13, 10,12, 18,23,8,7,6,30, 15, 21 11, 13, 10,12, 18,23,8,7,6,15,30, 21 11, 13, 10,12, 18,23,8,7,6,15,21, 30	пустое
11, 10, 12, 13, 18, 8, 7, 6, 15, 21, 23		После 1-ой
10, 11, 12,13, 8, 7, 6, 15, 18,21	23, 30	После 2-ой
10, 11, 12,8, 7, 6, 13, 15, 18	21, 23, 30	После 3-ей
10, 11, 8, 7, 6, 12,13, 15	18, 21,23, 30	После 4-ой
10, 8, 7, 6, 11, 12,13	15, 18, 21,23, 30	После 5-ой
8, 7, 6, 10, 11, 12	13, 15, 18, 21,23, 30	После 6-ой
7, 6, 8, 10, 11	12, 13, 15, 18, 21,23, 30	После 7-ой
6, 7, 8, 10	11, 12, 13, 15, 18, 21,23, 30	После 8-ой

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

Метод пузырька допускает несколько усовершенствований: В качестве первого усовершенствования можно предложить следующую оптимизацию: если в некоторый момент времени последовательность элементов окажется упорядоченной (это свойство легко проверяется отсутствием обменов при проходе по ), то конкатенация двух последовательностей и дает требуемую последовательность: в нашем примере 8-я фаза дает подобный результат. Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс k первого обмена. В этом случае все пары соседних элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно начинать с индекса k. Обратив внимание на то, что при сортировке пузырьком некоторые элементы очень медленно находят свои позиции (в нашем примере в первой фазе максимальный элемент сдвигается на 6 позиций, а минимальный только на одну), Кнут предложил усовершенствование этого алгоритма, который предполагает разбиение исходной последовательности на три части: и . Первоначально , и . В ходе своей работы алгоритм формирует в упорядоченную последовательность элементов, каждый из которых меньше или равен любого элемента из , в - упорядоченную последовательность элементов, каждый из которых больше или равен любому элементу из . В зависимости от прохода из поочередно извлекается максимальный или минимальный элемент (пополняется или ). Процесс продолжается до тех пор пока не станет упорядоченным (при проходе по элементам из не происходит ни одного обмена между элементами). Отсортированная последовательность получается в результате конкатенации последовательностей и . Такая модификация алгоритма получила название шейкер-сортировки. Анализ сложности [14] показывает, что такие улучшения, хотя и уменьшают общее число сравнений, но не изменяют порядок оценки времени работы алгоритма(для шейкер-сортировки - ). Шейкер-сортировку рекомендуется использовать в тех случаях, когда известно, что массив "почти упорядочен".

Простой выбор. Анализ пузырьковой сортировки показывает, что алгоритм за один проход вытаскивает максимальный элемент, проводя этот элемент через часть исходной последовательности. Поскольку результаты промежуточных обменов плохо используются в последующем, возникает вопрос: а нельзя ли уменьшить сложность алгоритма уменьшением количества обменов, если выбирать подходящий элемент в с последующей передачей его в ? Такой метод называется сортировкой с простым выбором. В качестве структуры данных в этом методе используется массив.Поскольку необходимо одновременно решать задачу поиска для и задачу слияния для , из извлекается и передается в максимальный элемент, который делает задачу слияния тривиальной (требующей константного числа операций). Первоначально в качестве рассматриваем всю исходную последовательность, а выбирается пустым. Найденный в максимальный элемент обменивается с последним элементом последовательности , и после обмена передается в . Учитывая, что при слиянии найденного максимального элемента, этот элемент не больше каждого из элементов, входящих в , слияние требует константного (не зависящего от числа элементов в ) числа шагов. Если при реализации алгоритма в качестве структуры данных использован массив, то число операций при поиске элемента из пропорционально числу входящих в него элементов. В этом случае получаем следующие оценки сложности работы алгоритма[23]:

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

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

Метод Шелла. В 1959 году Д.Шелл предложил алгоритм, который можно рассматривать как усовершенствование сортировки простыми включениями. Как уже упоминалось, алгоритм с простыми включениями достаточно эффективно работает на частично упорядоченных последовательностях. Поэтому, если на первых шагах производить упорядочивание далеко отстоящих элементов, и с каждым проходом сокращать расстояние между элементами, то можно улучшить сложностные показатели метода простых вставок. В варианте Шелла на -м шаге алгоритма текущая последовательность разбивается на подмножества элементов, которые отстоят друг от друга в исходной последовательности на расстоянии , с последующей сортировкой элементов в каждом множестве. Числа убывают от шага к шагу в определенном порядке (например, может быть , ,…,2,1), на последнем шаге сортируется вся последовательность (другое название алгоритма Шелла - сортировка включением с уменьшающимся расстоянием), однако эта операция производится на достаточно хорошо к этому моменту упорядоченной последовательности. Каждый проход алгоритма использует результаты предыдущих проходов. Основная идея состоит в перемешивании достаточно далеко расположенных друг от друга элементов с последующим уменьшением этого расстояния. Проиллюстрируем метод Шелла для нашего примера с шагами , , и .

Фактически метод Шелла на каждом шаге разбивает последовательность на подпоследовательности, локально упорядочивая каждую из них. Далее набор подпоследовательностей трактуется как единая последовательность, и процесс повторяется с новым разбиением. Оценка эффективности времени работы этого алгоритма достаточно сложна, она существенно зависит от выбора последовательности чисел . Кнут [14] показал, что достаточно эффективная реализация получается при следующей зависимости: , , . Наилучшая последовательность приращений неизвестна. Однако доказано, что числа этой последовательности не должны быть кратны друг другу[23]. Более подробный анализ метода Шелла приведен в [14]. Показано, при определенном выборе последовательности сложность алгоритма может оцениваться как . При реализации алгоритма для хранения последовательности используется массив. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность массива увеличивается при каждом новом просмотре данных.

Алгоритм сортировки с помощью кучи (пирамидальная сортировка). Рассмотрим алгоритм, улучшающий метод, связанный с простым выбором. Предположим, что при обновлении алгоритм передает из максимальный элемент (случай сортировки по неубыванию). Другими словами имеем абстрактный тип данных множество с операциями поиска максимального элемента и его удаления. АТД с такими операциями хорошо известен и называется очередью с приоритетами. Поскольку последовательная структура реализации такого типа данных (массив, линейный список) дает линейную оценку для реализации операции поиска максимального элемента, возникает вопрос об использовании древообразных структур, поддерживающих требуемое отношение порядка между элементами и учитывающих свойство транзитивности этого отношения. Такая структура существует и называется двоичной кучей. В силу свойства транзитивности при поиске максимального элемента отпадает необходимость попарного его сравнения с каждым элементом из . Негативной стороной такого подхода является необходимость поддержки основных свойств структуры при изменении . Покажем, что можно за шагов построить и, в дальнейшем, поддерживать структуру данных задающих частичный порядок на элементах множества .

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

Понятно, что любой начальный отрезок массива также обладает такими свойствами. Основное свойство, которое должно поддерживаться кучей заключается в следующем: значение элемента приписанному отцу вершины не меньше значения, приписанного самой вершине (). Очевидно, куча, для которой выполняется основное свойство, задает частичный порядок на элементах массива (а потому её ещё называют сортирующим деревом). Процедура построения отношения частичного порядка, является рекурсивной. Пусть отношение частичного порядка выполняется для вершин поддеревьев D1 и D2.

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

Рассмотрим пример построения кучи для последовательности 13, 11, 23, 10, 12, 18, 30, 8, 7, 6, 15, 21. Строка № (до) характеризует состояние массива до операции построения частичного порядка на поддереве, корень которого выделен жирным шрифтом. Строка № (после) характеризует массив после построения частичного порядка на соответствующем поддереве. В этой строке выделены элементы, которые участвуют (посредством обмена) в построении требуемого порядка.

№ шага		Рассма-три-ваемый элемент	Поддерево, где задается частичный порядок
1(до) 1(после) 2(до) 2(после) 3(до) 3(после) 4(до) 4(после) 5(до) 5(после) 6(до) 6(после)	13, 11, 23, 10, 12, 18, 30, 8, 7, 6, 15, 21 13, 11, 23, 10, 12, 21, 30, 8, 7, 6, 15, 18 13, 11, 23, 10, 12, 21, 30, 8, 7, 6, 15, 18 13, 11, 23, 10, 15, 21, 30, 8, 7, 6, 12, 18 13, 11, 23, 10, 15, 21, 30, 8, 7, 6, 12, 18 13, 11, 23, 10, 15, 21, 30, 8, 7, 6, 12, 18 13, 11, 23, 10, 15, 21, 30, 8, 7, 6, 12, 18 13, 11, 30, 10, 15, 21, 23, 8, 7, 6, 12, 18 13, 11, 30, 10, 15, 21, 23, 8, 7, 6, 12, 18 13, 15, 30, 10, 12, 21, 23, 8, 7, 6, 11, 18 13, 15, 30, 10, 12, 21, 23, 8, 7, 6, 11, 18 30, 15, 23, 10, 12, 21, 13, 8, 7, 6, 11, 18		18, 21 12, 6, 15 10, 8, 7 23, 21, 30, 18 11, 10, 15, 8, 7,6, 12 все дерево

Ниже на рисунке графически проиллюстрированы шаги по построению сортирующего дерева для нашего примера

Слева от нарисовано состояние поддерева до выполнения шага, а справа – после.

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

Построение сортирующего дерева, сложность - .
Для каждого начального отрезка массива длины найти максимальный элемент, поменять этот элемент с последним элементом начального отрезка массива, уменьшить число элементов 1 и переставляя элементы восстановить основное свойство кучи. Сложность -

Рассмотрим сортировку на нашем примере. В строках таблицы приведены состояния последовательностей и на момент обновления (после) и приведения последовательности к основному свойству кучи (до). Элементы, участвующие в обменах на соответствующих шагах выделены жирным шрифтом.

№ прохода
1(до) 1(после) 2(до) 2(после) 3(до) 3(после) 4(до) 4(после) 5(до) 5(после) 6(до) 6(после) 7(до) 7(после) 8(до) 8(после) 9(до) 9(после) 10(до) 10(после) 11(до) 11(после) 12(до) 12(после)	30, 15, 23, 10, 12, 21, 13, 8, 7,6, 11, 18 18, 15, 23, 10, 12, 21, 13, 8, 7,6, 11 23, 15, 21, 10, 12, 18, 13, 8, 7,6, 11 11, 15, 21, 10, 12, 18, 13, 8, 7,6 21, 15, 18, 10, 12, 11, 13, 8, 7,6 6, 15, 18, 10, 12, 11, 13, 8, 7 18, 15, 13, 10, 12, 11, 6, 8, 7 7, 15, 13, 10, 12, 11, 6, 8, 15, 12, 13, 10, 7, 11, 6, 8 8,12, 13, 10, 7, 11, 6, 13,12, 11, 10, 7, 8, 6 6, 12, 11, 10, 7, 8 12, 10, 11, 6, 7, 8 8, 10, 11, 6, 7 11, 10, 8, 6, 7 7,10, 8, 6 10,7, 8, 6 6, 7, 8 8, 7, 6 6,7 7, 6 Пусто	Пусто 23,30 23,30 21, 23,30 21, 23,30 18, 21, 23,30 18, 21, 23,30 15, 18, 21, 23,30 15, 18, 21, 23,30 13, 15, 18, 21, 23,30 13, 15, 18, 21, 23,30 12, 13, 15, 18, 21, 23,30 12, 13, 15, 18, 21, 23,30 11, 12, 13, 15, 18, 21, 23,30 11, 12, 13, 15, 18, 21, 23,30 10, 11, 12, 13, 15, 18, 21, 23,30 10, 11, 12, 13, 15, 18, 21, 23,30 8, 10, 11, 12, 13, 15, 18, 21, 23,30 8, 10, 11, 12, 13, 15, 18, 21, 23,30 7, 8, 10, 11, 12, 13, 15, 18, 21, 23,30 7, 8, 10, 11, 12, 13, 15, 18, 21, 23,30 6,7,8,10,11,12,13,15,18,21,23,30

Сортировка слиянием. Одной из основных идей, используемых при сортировке, является возможность разбиения задачи сортировки на подзадачи меньшей размерности с последующим объединением решений этих подзадач (метод разделяй и властвуй). Нечто подобное мы наблюдали в сортировке Шелла, но там объединение представляло фиктивную операцию. Поскольку решение каждой подзадачи представляет собой упорядоченную последовательность, то можно требовать от операции объединения сохранения установленного отношения порядка. В разобранных выше методах сортировки эта задача присутствует в вырожденном виде (упорядоченная последовательность сливается с одноэлементной последовательностью). Возникает вопрос, нельзя ли улучшить временные оценки, если как-то иначе разбивать последовательность на части. Ответ утвердительный при условии, что сортируемая последовательность разбивается, по крайней мере, на две части, число элементов в которых не являются константами, а представляют собой функцию от , где - число элементов исходной последовательности.

Процедура слияния двух упорядоченных последовательностей занимает центральное место в данном подходе и легко реализуется на последовательных структурах данных. Разберем эту процедуру более подробно. Предположим, что имеются две отсортированные последовательности и , содержащие соответственно и элементов. Процедура слияния предусматривает асинхронное сканирование этих последовательностей слева направо, которое реализуется посредством сдвига указателя на активный элемент последовательности. На каждом шаге алгоритма происходит сравнение активных элементов с отбором минимального или максимального (в зависимости от характера сортировки) из них в некоторую дополнительную последовательность и сдвигом указателя для последовательности, из которой был извлечен элемент. Если достигается конец одной из последовательностей (допустим последовательности ), то результирующая последовательность получается как конкатенация формируемой последовательности с остатком последовательности . Несложно показать, что эта процедура имеет временную сложность . Отметим, что при и в определенном смысле невозможно обойтись без дополнительной последовательности [24].

Поскольку каждая подзадача может быть решена таким же образом, то легко построить рекурсивный алгоритм, использующий слияние последовательностей, длина которых зависит от шага алгоритма. Проще всего продемонстрировать работу алгоритма для случая, когда и на каждом шаге последовательность делится на две равные части. Рассмотрим два массива и размерности , первый из которых содержит исходную последовательность. На первом шаге работы алгоритма производится слияние одноэлементных последовательностей, состоящих из элементов и для . Результаты слияния размещаются в массиве . На следующем шаге алгоритм сливает стоящие по соседству последовательности длины 2 массива с размещением результата в массив . На последнем шаге сливаются последовательности длины . Логически алгоритм описывается в виде дерева высоты , листьям которого сопоставлены элементы исходной последовательности, вершинам -го уровня упорядоченные последовательности длины , состоящие из элементов, приписанных листьям-потомкам этих вершин. Соответственно корень дерева кодирует упорядоченную последовательность всех элементов исходной последовательности.

Пример работы алгоритма на последовательности 13, 11, 23, 10, 12, 18, 30, 8, 7, 6, 15, 21

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

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

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

В настоящее время этот метод считается в определенном смысле наилучшим. Этот факт вызывает удивление, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представляет собой простейшую версию обменной сортировки. Ч.Хоар, автор этого метода, дал ему название "Быстрая сортировка" ("Quicksort").

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

Сортировка разделением является реализацией подобного подхода: в массиве случайным образом выбирается некоторое значение , после чего запускается процедура разделения массива: массив сканируется слева направо с целью поиска элемента . Аналогичное производится сканирование справа налево для поиска элемента . При условии, что такие элементы существуют, они обмениваются, и процесс продолжается до тех пор, пока оба просмотра не встретятся на некотором элементе массива. В результате массив окажется разбитым на две части – левую , в которой значения ключей будут меньше или равны , и правую со значениями ключей, больших или равных . Ниже показан процесс разбиения массива относительно числа 6:

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

quickSort (массив a, верхняя граница N) {

Выбрать разделяющий элемент p - середину массива

Разделить массив по этому элементу

Если подмассив слева от p содержит более одного элемента,

вызвать quickSort для него.

Если подмассив справа от p содержит более одного элемента,

вызвать quickSort для него.

}

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

Поскольку поиск медианы в множестве[25] представляет отдельную задачу (также требующую своего ресурса времени), то рассматривают более простые способы выбора значения, относительно которого строится разбиение. Однако это позволяет получить оценку только в среднем. Разбивающее значение можно выбирать случайным образом (вероятность выбора максимального элемента в качестве разделяющего при каждом разбиении сортируемой подпоследовательности очень мала, при n = 1024 она меньше ) или путем усреднения небольшого числа элементов, выбранных из массива. Распространенный и достаточно эффективный метод заключается в выборке трех элементов (к примеру, из начала, середины и конца последовательности) и вычисление их среднего значения. Анализ различных способов выбора разделяющего элемента, а также алгоритмов разбиения последовательности приведен в [4].

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

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

Сканируя массив, для каждого числа от 0 до m подсчитываем, сколько раз оно встречается в массиве. С этой целью заводится счетчиков, и -ый счетчик подсчитывает число элементов последовательности равное . После этого исходный массив можно переписать в порядке возрастания, используя сведения о повторяемости каждого числа. Если , то время работы этого алгоритма – линейно, но используется дополнительной памяти. В этом алгоритме используется только информация о значении элементов.

Лексикографическая сортировка Данный метод является обобщением предыдущего, при условии, что ключи задаются векторами конечной размерности. Имеется массив из n чисел от 0 до (2 в степени k), каждое из которых рассматривается как k-битовое слово (пример реализации приведен во введении). При реализации поразрядной сортировки существенным образом использует свойство устойчивости.

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

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

⇐ Предыдущая 1 2 3 4 5 6 789 10 Следующая ⇒