Сортировка практически важная и теоретически интересная задача, связанная с распределением некоторых данных из заданной совокупности в определённом порядке.
Сортировка стала важным предметом вычислительной математики, т.к. она отнимает значительную часть времени работы ЭВМ. 25% всего времени вычислений расходуется на сортировку данных, поэтому построение эффективных алгоритмов сортировки является важной (необходимой) задачей.
К сожалению, нет алгоритма сортировки, который был бы наилучшим в любом случае. Эффективность алгоритма сортировки зависит от многих факторов, например:
· от числа сортируемых элементов;
· все ли элементы могут быть помещены в доступную оперативную память;
· до какой степени элементы уже отсортированы;
· каковы диапазон и распределение значений сортируемых элементов;
· способ ввода информации и данных;
· какова длина, сложность и требования к памяти алгоритма сортировки;
· предполагается ли, что элементы будут периодически добавляться или исключаться;
· можно ли элементы сравнивать параллельно.
Сортировка применяется при трансляции программ, когда составляются таблицы символов, а также является важным средством для ускорения работы практически любого алгоритма, в котором часто нужно обращаться к определённым элементам.
Задача сортировки – это расположение элементов данных из некоторой совокупности, в определённом порядке.
Обычно сортируемые элементы представляют собой записи данных определённого вида. Каждая запись имеет поле ключа и поле информации. В сортировки участвуют не целиком элементы данных, а только их часть, называемая ключом сортировки.
Тогда, сортировкой называют операцию, упорядочивающую множество элементов по ключам, на которых определено отношение порядка.
Частичным порядком на множестве S называется двухместное отношение R такое, что для любых a, b, c Î S выполняются
1. рефлексивность – aRa;
2. транзитивность – если aRb и bRc, то aRc;
3. антисимметричность – если aRb и bRa, то a=b.
Частичного порядка обладают отношения £ (для целых чисел) и отношение Í (включения в множество).
Линейным или полным порядком на множестве S называется такой частичный порядок R на S, что для любых двух элементов a, b выполняется либо aRb либо bRa. Отношение £ на множестве целых чисел обладает свойством линейного порядка, а отношение включения в множество Í - нет.
Традиционные методы сортировки делят на внутренние и внешние. Внутренние методы - это такие методы, которые могут применяться с приемлемой производительностью только к тем спискам данных, которые целиком помещаются в основной памяти процессора. Внешние методы - это такие методы, которые приемлемы для файлов данных, которые слишком велики, чтобы поместиться в основной памяти, и поэтому должны в процессе сортировки располагаться на устройствах внешней памяти. Слово список часто обозначает набор записей, расположенных в основной памяти.
В процессе внешней сортировки часть файла считывается в основную память, там упорядочивается, а затем переписывается на внешнее устройство. Этот процесс повторяется несколько раз. Внутренние методы используются для перестановки данных, обрабатываемых между их пересылками.
Сортировки могут быть охарактеризованы сложностью метода определения последовательности сравнений, комбинацией используемых методов, основным способом упорядочения и объёмом необходимой памяти.
По числу сравнений различают линейные и нелинейные сортировки. Линейные алгоритмы рассматривают сортируемый список как линейную последовательность элементов, при этом элементы выбираются последовательно сверху или снизу списка один за другим. Нелинейные методы предполагают наличие структуры у списков, которые они сортируют. Они наиболее эффективны, когда списки рассматриваются как двоичные деревья.
Простая сортировка использует один и тот же метод в процессе сортировки. Простые алгоритмы не обязательно являются не сложными. Если разработчик сортировки на разных этапах использует различные методы сортировки, то такой алгоритм называется комбинированным.
В сравнительном алгоритме данные упорядочиваются по относительной величине ключей в списке. Распределительный метод обследует ключ целиком, либо символ за символом. Распределительные сортировки полезны, когда о сортируемых данных известно многое, например, распределение ключей по некоторым интервалам, длина ключей, число записей.
В минимальном по памяти методе память требуется только для программы и упорядочиваемого списка. Не минимальные по памяти методы требуют память и для копии исходного списка. Преимущество минимальной по памяти сортировки в том, что она позволяет сортировать большие списки в основной памяти, хотя и ценой продолжительности сортировки.
К фундаментальным алгоритмам внутренней сортировки относятся алгоритмы: линейного выбора, линейного выбора с обменом (метод "пузырька"), просеивания (так же "линейная вставка с обменом" или "челночная сортировка"), линейной вставки.
Разберём все эти методы.
Линейный выбор: выбирается наименьший элемент и выводится на печать, в исходной последовательности заменяется фиктивным элементом.
Метод "пузырька":
"Челночная сортировка": при каждом просмотре меняются местами два соседних элемента в порядке сортировки, подсчитывается число обменов, если после просмотра это число равно 0, то сортировка закончена.
Линейная вставка: элемент из исходной последовательности размещается в выходной между большим и меньшим его элементом.
Метод Шелла.Сортировка Шелла является расширением сортировки просеиванием (вычерпыванием) и минимальным по памяти методом. На каждом просмотре шаг между сравниваемыми элементами определяется путём сокращения вычисленного исходного шага. На последнем просмотре он сокращается до 1. Для расчёта шага просмотра элементов используются разные алгоритмы, но наиболее интересным является алгоритм Хиббарда.
Цель метода на ранних просмотрах - сократить число вторичных сравнений и обменов на более поздних просмотрах. В этом методе элементы могут совершать большие скачки к нужным позициям на ранних просмотрах, а не передвигаться на одну позицию за один раз.
Наиболее общей формой внешней сортировки является сортировка-слияние.
Сортировка слиянием: сущность этого метода состоит в том, что процесс сортировки состоит из двух этапов - этапа сортировки и этапа слияния.
На этапе сортировки (или распределения) за один раз читается столько данных, сколько может поместиться в имеющейся памяти, после чего в памяти некоторым образом строятся упорядоченные строки данных. Эти строки переписываются из памяти в соответствии с алгоритмом распределения, созданным специально под нужное слияние. В большинстве алгоритмов все данные просматриваются на этапе сортировки до слияния. В начале слияния есть семейство строк, распределённых по устройствам. Последующее слияние формирует единую упорядоченную строку.
Рассмотрим пример сортировки вычерпыванием.
Задана последовательность целых чисел а1, а2, …, аn, каждое из которых заключено в интервале [0, m-1].
Если число m не слишком велико, то заданную последовательность можно упорядочить следующим образом:
1. организуем m пустых очередей по одной для каждого целого числа от 0 до m-1. Каждую такую очередь назовём черпаком.
2. Просмотрим последовательность а1, а2, …, аn слева на право, помещая элемент аi в очередь с номером аi.
3. Сцепим эти очереди (содержимое (i+1)-ой очереди приписываем к концу i-ой очереди) и получим в результате упорядоченную последовательность.
Т.к. любой элемент можно поместить в i-ю очередь за постоянное время, то n элементов можно поместить в очереди за время O(n). Сцепление m очередей требует времени порядка O(m). Если m=O(n), то этот алгоритм сортирует n целых чисел за время порядка O(n). Назовём этот алгоритм сортировкой вычерпыванием.
Рассмотрим пример такой сортировки.
Сортировка поразрядным группированием. Эта сортировка начинается с анализа самой младшей значащей цифры ключевого слова. Затем все величины с одинаковыми значащими цифрами объединяются в группы.
После того как все величины распределены по данному правилу содержимое групп располагается по возрастанию значения анализируемого разряда и процесс повторяется до тех пор, пока не останется цифр слева.
Система счисления с основанием p требует p групп (очередей или черпаков).
Следующим обобщением сортировки вычёрпыванием будет распространение её на кортежи неодинаковой длины, которые мы будем называть цепочками.
Если самая длинная цепочка имеет длину k, то можно любую цепочку дополнить специальным символом до длины k и затем применять алгоритм поразрядного группирования (или как его ещё называют – алгоритм лексико-графической сортировки).
Следующим обобщением сортировки вычёрпыванием будет распространение её на кортежи неодинаковой длинны, которые мы будем называть цепочками.
Если самая длинная цепочка имеет длину k , то можно каждую цепочку дополнить специальными символами до длины k и затем применить алгоритм поразрядного группирования. Если же длинных цепочек будет мало, по сравнению с общим количеством элементов последовательности, то ранее рассмотренный алгоритм неэффективен.
Рассмотрим алгоритм, сортирующий n-элементную последовательность цепочек различной длинны, компонентами которых служат числа между 0 и m-1; время работы этого алгоритма на такой последовательности равно О(m+l*), где li – длина i-ой цепочки, а l*=. Этот алгоритм полезен в ситуации, когда числа m и l* имеют одинаковый порядок O(n).
Суть этого алгоритма в том, что сначала он сначала располагает цепочки в порядке убывания длин. Пусть lmax – длина самой длинной цепочки. Тогда сортировка вычёрпыванием применяется lmax раз.
Но первое такое применение (по самой правой компоненте) сортируют лишь цепочки длины lmax. Второе применение сортирует (в соответствии с (lmax – 1)-й компонентой) те цепочки, длина которых не менее lmax – 1, и т.д.
Вход: Последовательность цепочек (кортежей) А1, А2, …, Аn, компоненты которых представлены целыми числамии от 1 до m – 1. Пусть li – длина цепочки Ai = (ai1, ai2, … , aili) и lmax – наибольшее из чисел li.
Выход: Перестановка В1, В2, …, Вn цепочек Ai такая, что В1 ≤ В2 ≤ … ≤ Вn .
Метод:
1. формирование списков симвролов, которые появляются в l компоненте одной или более цепочек. Строим пары (l, ail) – для каждой компоненты каждой цепочки. Затем сформируем упорядоченный список: НЕПУСТ[l].
2. Определяем длину каждой цепочки, формируем список ДЛ[l], в котором содержатся указатели всех цепочек длины l.
3. Сортируем цепочки по компонентам, как в предыдущих алгоритмах с учётом списков НЕПУСТ и ДЛ.
. Этот алгоритм полезен в ситуации, когда числа m и l* имеют одинаковый порядок O(n).