Поиск и сортировка. Последовательный поиск (метод грубой силы). Двоичный поиск (метод декомпозиции)

Поиск и сортировка

Последовательный поиск (метод грубой силы)

Найти в конечном множестве (массиве) X элемент x, удовлетворяющий совокупности условий K(x). Алгоритм: 1. Взять из множества X еще не рассмотренный элемент и проверить совокупность условие K(x). 2. Если какое-либо условие не выполнено, то перейти к п.1. 3. Если выполнены все условия, то x является решением. Если возможно несколько решений и требуется найти все их, то вернуться к п.1, пока не будут перебраны все элементы из множества X. Элемента x может не быть в множестве X.

Последовательный поиск (метод грубой силы)

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

Пример 1. Последовательный поиск элемента в массиве.

Поиск элемента A в массиве A1, A2, …, An. В наихудшем случае (элемента в массиве нет или он находится на последнем месте) необходимо выполнить n сравнений T(n) = c*n, с – время одного сравнения. В среднем Tср(n) ~ c*n/2. В лучшем случае достаточно произвести только одно сравнение, когда элемент находится в начале массива.

Пример 1. Последовательный поиск элемента в массиве.

#include <stdio.h> int sequential_search(int*items, int count, int key); void main() { int array[10] = {2,5,1,7,3,8,0,4,6,9}; int x, r; printf(“Введите целое число: “); scanf(“%d”,&x); if((r = sequential_search(array, 10, x)) == -1) printf(“Этого числа нет в массиве”); else printf(“Это число есть массиве на %d позиции”,r); }

Пример 1. Последовательный поиск элемента в массиве.

int sequential_search(int*items, int count, int key) { register int t; for(t = 0: t < count; t++) if(key == items[t]) return t+1; return -1; }

Двоичный поиск (метод декомпозиции)

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

Двоичный поиск (метод декомпозиции)

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

Двоичный поиск (метод декомпозиции)

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

Двоичный поиск (метод декомпозиции)

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

Пример 2. Двоичный поиск элемента в массиве.

Поиск элемента A в массиве A1, A2, …, An. В наихудшем случае (элемента в массиве нет или он находится при последнем сравнении) необходимо выполнить n сравнений T(n) = c*log2n, с – время одного сравнения. В лучшем случае достаточно произвести только одно сравнение, когда элемент находится в середине массива. Эффективность двоичного поиска в среднем оценить сложнее. Сложный анализ показывает, что среднее количество сравнений ключей только немного меньше такового в наихудшем случае.

Пример 2. Двоичный поиск элемента в массиве.

#include <stdio.h> int binary_search(int*items, int count, int key); void main() { int array[10] = {0,1,2,3,4,5,6,7,8,9}; int x, r; printf(“Введите целое число: “); scanf(“%d”,&x); if((r = binary_search(array, 10, x)) == -1) printf(“Этого числа нет в массиве”); else printf(“Это число есть массиве на %d позиции”,r); }

Пример 2. Двоичный поиск элемента в массиве.

int binary_search(int*items, int count, int key) { int low, high, mid; low = 0; high = count – 1; while(low <= high) { mid = (low + high)/2; if(key < items[mid]) high = mid – 1; else if(key > items[mid]) low = mid + 1; else return mid; } return -1; }

Функции поиска

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

Сортировка

Общие понятия

Сортировка – процесс перегруппировки однотипных элементов структуры данных в определенном порядке (по возрастанию или убыванию). Цель сортировки – облегчить последующие поиск, обновление, исключение, включение элементов в структуру данных. Разработано множество алгоритмов сортировки, однако нет алгоритма