Сортировка, выпуклые оболочки

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

[Н.Вирт Алгоритмы+Структуры данных = Программы]

Задача сортировки

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

Математически задача сортировки формулируется следующим образом:

Задано конечное множество объектов . Требуется построить некоторую биекцию , отображающую начальный отрезок натурального ряда на объекты исходной последовательности , сохраняющую отношение : , где . Отношение назовем отношением предшествования. Содержательный смысл термина «предшествование» зависит от характера задачи и может быть для различных множеств, вообще говоря, различным (больше, меньше, лучше, красивее, выше и пр.). Для определенности, в дальнейшем предполагается использовать термины «меньше» и «больше» как это принято при определении отношения частичного порядка. Отношение предшествования на множестве элементов вводится таким образом, чтобы для любых трех значений и выполнялись условия[14]:

1. выполняется только одно из трех соотношений , или (закон трихотомии).
2. если и , то (закон транзитивности)

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

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

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

Задача сортировки относится к числу фундаментальных задач при изучении алгоритмов, что неудивительно – отношение порядка занимает фундаментальное положение в математике в целом. Причинами такого положения вещей являются:

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

2. Сортировка – одна из немногих задач, для которой доказаны нетривиальные нижние оценки. Наличие нижних оценок позволяет оценить качество предлагаемых алгоритмов.

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

4. Введение ограничений на вычислительные ресурсы (с одной стороны - времени, а с другой - памяти) приводит к целой серии алгоритмов, использующих различные структуры данных. Можно анализировать и сравнивать между собой достоинства и недостатки применяемых структур (по паре критериев – времени и памяти).

Без потери общности можно считать, что элементы исходного множества просматриваются в определенном порядке, поэтому в дальнейшем речь будет идти о задаче сортировки последовательности объектов. Перед решением задачи необходимо понимать, как должны выглядеть конечные данные: должен ли алгоритм физически переставлять элементы исходной последовательности согласно значениям функции , или должен быть построен набор указателей на элементы исходной последовательности, которые служат реализацией функции . Сами объекты могут иметь достаточно сложную структуру. Например, при сортировке сотрудников некоторой фирмы каждый объект может содержать информацию о фамилии, имени, отчеству, возрасту, домашнем адресе, семейном положении, о времени работы на фирме и пр. При этом информация, необходимая для сортировки может содержаться только в некоторой части указанной структуры (например, необходимо проводить сортировку по фамилии, имени и возрасту). Назовем поля, которые хранят существенную для выполнения сортировки информацию – ключевыми, а остальные поля – дополнительными. Дополнительные поля перемещаются вместе с ключевыми полями. Однако перемещение дополнительных полей связано с определенными накладными расходами. При большом объеме дополнительных данных разумно информацию о каждом объекте разбить на два блока, первый из которых содержит ключевые поля и указатель на блок, содержащий все дополнительные поля. Поскольку информация, связанная с дополнительными полями не участвует в процессе сортировки, можно без ограничения общности считать, что сортируемые объекты состоят только из ключевых полей. При сортировке также необходимо различать ситуации, когда множество ключевых полей воспринимается как единый объект, или мы рассматриваем их как элементы иерархической структуры. Первое возможно, если имеется кодирующая функция, приписывающая значениям сложного ключа некоторое число. В этом случае задача сортировки сводится к сортировке последовательности по значениям простого (числового) ключа, и к временной сложности алгоритма сортировки необходимо добавлять время вычисления значения этого ключа. Если по каким-то причинам применение функция кодировки не желательно (причиной может быть сложность кодирования), то можно сортировку осуществлять по отдельным полям составного ключа с учетом имеющейся иерархии. В этом случае важным свойством алгоритма сортировки является его устойчивость. Метод сортировки называется устойчивым, если относительный порядок элементов с одинаковыми ключами не меняется при сортировке. Устойчивость сортировки бывает необходимой, если элементы дополнительно упорядочиваются по каким-то вторичным ключам, т.е. по свойствам не отраженным в первичном ключе. [23].

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

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