Сортировки и порядковые статистики.
Сортировка практически важная и теоретически интересная задача, связанная с распределением некоторых данных из заданной совокупности в определённом порядке.
Сортировка стала важным предметом вычислительной математики, т.к. она отнимает значительную часть времени работы ЭВМ. 25% всего времени вычислений расходуется на сортировку данных, поэтому построение эффективных алгоритмов сортировки является важной (необходимой) задачей.
К сожалению, нет алгоритма сортировки, который был бы наилучшим в любом случае. Эффективность алгоритма сортировки зависит от многих факторов, например:
от числа сортируемых элементов;
все ли элементы могут быть помещены в доступную оперативную память;
до какой степени элементы уже отсортированы;
каковы диапазон и распределение значений сортируемых элементов;
способ ввода информации и данных;
какова длина, сложность и требования к памяти алгоритма сортировки;
предполагается ли, что элементы будут периодически добавляться или исключаться;
можно ли элементы сравнивать параллельно.
Сортировка применяется при трансляции программ, когда составляются таблицы символов, а также является важным средством для ускорения работы практически любого алгоритма, в котором часто нужно обращаться к определённым элементам.
Задача сортировки.
Задача сортировки – это расположение элементов данных из некоторой совокупности, в определённом порядке.
Обычно сортируемые элементы представляют собой записи данных определённого вида. Каждая запись имеет поле ключа и поле информации. В сортировки участвуют не целиком элементы данных, а только их часть, называемая ключом сортировки.
Тогда, сортировкой называют операцию, упорядочивающую множество элементов по ключам, на которых определено отношение порядка.
Частичным порядком на множестве S называется двухместное отношение R такое, что для любых a, b, c S выполняются
рефлексивность – aRa;
транзитивность – если aRb и bRc, то aRc;
антисимметричность – если aRb и bRa, то a=b.
Частичного порядка обладают отношения (для целых чисел) и отношение (включения в множество).
Линейным или полным порядком на множестве S называется такой частичный порядок R на S, что для любых двух элементов a, b выполняется либо aRb либо bRa. Отношение на множестве целых чисел обладает свойством линейного порядка, а отношение включения в множество - нет.
Традиционные методы сортировки делят на внутренние и внешние. Внутренние методы - это такие методы, которые могут применяться с приемлемой производительностью только к тем спискам данных, которые целиком помещаются в основной памяти процессора. Внешние методы - это такие методы, которые приемлемы для файлов данных, которые слишком велики, чтобы поместиться в основной памяти, и поэтому должны в процессе сортировки располагаться на устройствах внешней памяти. Слово список часто обозначает набор записей, расположенных в основной памяти.
В процессе внешней сортировки часть файла считывается в основную память, там упорядочивается, а затем переписывается на внешнее устройство. Этот процесс повторяется несколько раз. Внутренние методы используются для перестановки данных, обрабатываемых между их пересылками.
С
ортировки
могут быть охарактеризованы сложностью
метода определения последовательности
сравнений, комбинацией используемых
методов, основным способом упорядочения
и объёмом необходимой памяти.
По числу сравнений различают линейные и нелинейные сортировки. Линейные алгоритмы рассматривают сортируемый список как линейную последовательность элементов, при этом элементы выбираются последовательно сверху или снизу списка один за другим. Нелинейные методы предполагают наличие структуры у списков, которые они сортируют. Они наиболее эффективны, когда списки рассматриваются как двоичные деревья.
Простая сортировка использует один и тот же метод в процессе сортировки. Простые алгоритмы не обязательно являются не сложными. Если разработчик сортировки на разных этапах использует различные методы сортировки, то такой алгоритм называется комбинированным.
В сравнительном алгоритме данные упорядочиваются по относительной величине ключей в списке. Распределительный метод обследует ключ целиком, либо символ за символом. Распределительные сортировки полезны, когда о сортируемых данных известно многое, например, распределение ключей по некоторым интервалам, длина ключей, число записей.
В минимальном по памяти методе память требуется только для программы и упорядочиваемого списка. Не минимальные по памяти методы требуют память и для копии исходного списка. Преимущество минимальной по памяти сортировки в том, что она позволяет сортировать большие списки в основной памяти, хотя и ценой продолжительности сортировки.
К фундаментальным алгоритмам внутренней сортировки относятся алгоритмы: линейного выбора, линейного выбора с обменом (метод "пузырька"), просеивания (так же "линейная вставка с обменом" или "челночная сортировка"), линейной вставки.
Разберём все эти методы.
Линейный выбор: выбирается наименьший элемент и выводится на печать, в исходной последовательности заменяется фиктивным элементом.
Метод "пузырька":
"Челночная сортировка": при каждом просмотре меняются местами два соседних элемента в порядке сортировки, подсчитывается число обменов, если после просмотра это число равно 0, то сортировка закончена.
Линейная вставка: элемент из исходной последовательности размещается в выходной между большим и меньшим его элементом.
Метод Шелла. Сортировка Шелла является расширением сортировки просеиванием (вычерпыванием) и минимальным по памяти методом. На каждом просмотре шаг между сравниваемыми элементами определяется путём сокращения вычисленного исходного шага. На последнем просмотре он сокращается до 1. Для расчёта шага просмотра элементов используются разные алгоритмы, но наиболее интересным является алгоритм Хиббарда.
Цель метода на ранних просмотрах - сократить число вторичных сравнений и обменов на более поздних просмотрах. В этом методе элементы могут совершать большие скачки к нужным позициям на ранних просмотрах, а не передвигаться на одну позицию за один раз.
Наиболее общей формой внешней сортировки является сортировка-слияние.
Сортировка слиянием: сущность этого метода состоит в том, что процесс сортировки состоит из двух этапов - этапа сортировки и этапа слияния.
На этапе сортировки (или распределения) за один раз читается столько данных, сколько может поместиться в имеющейся памяти, после чего в памяти некоторым образом строятся упорядоченные строки данных. Эти строки переписываются из памяти в соответствии с алгоритмом распределения, созданным специально под нужное слияние. В большинстве алгоритмов все данные просматриваются на этапе сортировки до слияния. В начале слияния есть семейство строк, распределённых по устройствам. Последующее слияние формирует единую упорядоченную строку.
Рассмотрим пример сортировки вычерпыванием.