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

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

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

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

Пусть надо упорядочить п элементов m ₁, m ₂, …, m_n, которые назовем записями. Каждойзаписи m_j поставим в соответствие свой ключ k_j, который и будет управлять процессом сортировки. Помимо ключа запись может содержать и дополнительную информацию, которая не влияет на сортировку, но всегда остается в этой записи. Задача заключается в нахождении такой перестановки , , …, , записей m ₁, m ₂, …, m_n, после которой ключи будут располагаться в неубывающем (невозрастающем) порядке:

≤ ≤ … ≤ ( ≥ ≥ … ≥ )

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

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

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

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

Дата добавления: 2014-11-16