1. Основные понятия алгоритмизации и программирования

9.4. Бинарный поиск

Наиболее эффективным и распространенным методом непоследовательного поиска в одномерных упорядоченных массивах является бинарный поиск, который называют также методом половинного деления, методом дихотомии, методом логарифмического поиска или методом деления пополам. Основная идея бинарного поиска состоит в том, что сначала искомый элемент х сравнивается со средним элементом массива а[n]. Результат сравнения либо приводит к решению задачи, либо позволяет определить, в какой части массива – левой или правой – продолжать поиск. После каждой такой итерации область поиска сокращается вдвое и не более чем через [log2n] сравнений мы закончим поиск, то есть либо попадем на элемент х, либо покажем, что х не принадлежит массиву а[n]. Например, при n = 1000 бинарный поиск в 100 раз быстрее последовательного, а при n = 1000000 – в 50000 раз. Разумеется, если массив неупорядоченный, то применить к нему бинарный поиск нельзя. Таким образом, факт упорядоченности элементов в массиве играет ключевую роль при бинарном поиске.

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

От порядка расположения данных в памяти ЭВМ, во многом зависит скорость и простота выполнения алгоритмов, предназначенных для обработки этих данных. Поэтому в программировании часто возникает задача перегруппировки данных в невозрастающем или неубывающем, порядке. Такая задача называется упорядочением или сортировкой элементов данной структуры, в простейшем случае – элементов одномерного массива.
Задача сортировки связана со многими важными приложениями, кроме того, служат хорошей иллюстрацией анализа сложности алгоритмов и тем самым позволяют разумно выбирать лучшие среди, казалось бы, равноценных методов. Каждый из алгоритмов сортировки имеет свои достоинства и недостатки, и выбирать алгоритмы нужно, исходя из конкретной постановки задачи. Выбор алгоритма сортировки существенно зависит от структуры обрабатываемых данных, поэтому все методы сортировки подразделяют на два класса: внутренний (сортировка массивов) и внешний (сортировка последовательных файлов). Различие: при внутренней сортировке все данные хранятся в оперативной памяти ЭВМ, а при внешней - во внешней памяти. При внутренней сортировке имеются более гибкие возможности для построения алгоритмов, так как все данные выстроены в виде массива и как бы лежат перед пользователем, он видит каждый элемент и имеет к нему прямой доступ. При внешней сортировке доступ к данным ограничен, поскольку они из-за своего размера в оперативной памяти не помещаются.
Уточним математическую постановку задачи сортировки данных [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 передаются в результирующий массив В, представляют значительно меньший интерес.