Постановка задачи сортировки данных

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

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

Уточним математическую постановку задачисортировки данных [7].

Пусть надо упорядочитьп элементов m1, m2, …, mn, которые назовем записями. Каждойзаписи mj поставим в соответствие свой ключ kj, который и будет управлять процессом сортировки. Помимо ключа запись может содержать и дополнительную информацию, которая не влияет на сортировку,но всегда остается в этой записи. Задача заключается в нахождении такой перестановки , , …, , записей m1, m2, …, mn, после которой ключи будут располагаться в неубывающем (невозрастающем) порядке:

≤ … ≤ ( ≥ … ≥ )

Сортировка называетсяустойчивой,если она удовлетворяет дополнительномуусловию: записи с одинаковыми ключами остаются в прежнем порядке, т.е. pi < pj, если и i < j.

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

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

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