9.3. Последовательный (линейный) поиск

Простейшим методом поиска является последовательный просмотр таблицы, одномерного массива или строки до нахождения элемента с требуемыми свойствами или установления факта, что такого элемента нет. Для массива, данные в котором не упорядочены сортировкой, единственный путь поиска заданного элемента состоит в сравнении каждого элемента массива с заданным. При совпадении некоторого элемента массива с заданным, его позиция в массиве фиксируется. Этот алгоритм называется последовательным, или линейным, поиском. Ядром такого алгоритма является цикл по индексу массива. Так, если в массиве int a[n] нужно найти введенное с клавиатуры целое число х, о котором никакой дополнительной информации нет, то соответствующий цикл можно записать следующим образом:

for (i = 0; i < n; i++) if (a[i] == x) k = i;

Этот способ решения обладает двумя существенными недостатками:

• если значение х встречается в массиве несколько раз, то будет найдено последнее из них;

• после того, как нужное значение уже найдено, массив просматривается до конца, то есть всегда выполняется п сравнений.

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

while ((i < n) && (a[i] != x)) i++;

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

Наиболее эффективным и распространенным методом непоследовательного поиска в одномерных упорядоченных массивах является бинарный поиск, который называют также методом половинного деления, методом дихотомии, методом логарифмического поиска или методом деления пополам. Основная идея бинарного поиска состоит в том, что сначала искомый элемент х сравнивается со средним элементом массива а[n]. Результат сравнения либо приводит к решению задачи, либо позволяет определить, в какой части массива - левой или правой - продолжать поиск. После каждой такой итерации область поиска сокращается вдвое и не более чем через [log₂n] сравнений мы закончим поиск, то есть либо попадем на элемент х, либо покажем, что х не принадлежит массиву а[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 передаются в результирующий массив В, представляют значительно меньший интерес.