Алгоритмы поиска, выборки и сортировки.

Алгоритмы поиска

Алгоритм последовательного поиска (АПП) последовательно просматривает по одному элементу списка, начиная с первого, до тех пор, пока не найдет целевой элемент. Предполагается, что список не отсортирован. Наихудший случай: целевой элемент стоит в списке последним или его вовсе нет в списке. Средний случай: поиск всегда завершается успешно, или иногда целевое значение в списке отсутствует.

Алгоритм двоичного поиска (АДП): двоичный поиск осуществляется на отсортированном списке. Идея в том, что список делится пополам, берется средний эл-т и сравнивается с целевым эл-том. При сравнении возможен один из трех результатов: значения равны, целевое значение меньше элемента списка, либо целевое значение больше элемента списка. В первом, и наилучшем, случае поиск завершен. В остальных двух случаях мы можем отбросить половину списка. Когда целевое значение меньше среднего элемента, мы знаем, что если оно имеется в списке, то находится перед этим средним элементом. Когда же оно больше среднего элемента, мы знаем, что если оно имеется в списке, то находится после этого среднего элемента. Этого достаточно, чтобы мы могли одним сравнением отбросить половину списка. При повторении этой процедуры мы сможем отбросить половину оставшейся части списка. В наихудшем случае число проходов равно k = log2(N +1). Средний случай A(N)≈ log2(N +1)-1.

Существуют и другие алгоритмы поиска:

- алгоритм перебора - модификация алгоритма линейного поиска; находит k-тый по величине элемент в списке;

- дерево двоичного поиска – использует бинарное дерево для хранения элементов;

- интерполирующий поиск (предсказывающий поиск, поиск по словарю);

- линейный поиск — находит элемент в неотсортированном списке;

- поиск в глубину — проходит граф ветка за веткой;

- поиск в ширину — проходит граф уровень за уровнем;

- поиск по первому наилучшему совпадению - проходит граф в порядке важности, используя очередь приоритетов;

- троичный поиск - находит элемент в отсортированном списке.

Алгоритмы сортировки

Сортировка вставками: на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора. Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — θ(n²).

Пузырьковая сортировка: алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

Сортировка слиянием: алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Сортируемый массив разбивается на две части примерно одинакового размера. Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом. Два упорядоченных массива половинного размера соединяются в один. Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).

Существуют и другие алгоритмы сортировки:

- наивная сортировка — генерация всех n! возможных перестановок и проверка на отсортированность;

- быстрая сортировка — с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине;

- поразрядная сортировка — сортирует строки буква за буквой;

- сортировка с помощью двоичного дерева;

- сортировка методом выбора — наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка;

- сортировка Шелла — попытка улучшить сортировку вставками;

Алгоритмы выборки

Иногда нам нужен эл-т из списка, обладающий некоторыми специальными св-ми, а не имеющий некоторое конкретное значение. Например, в списке сотрудников найти среднего по возрасту или найти 5 сотрудников с наименьшей оплатой труда. В более общем случае нас может интересовать запись с К-ым по величине значением поля. Один из способов найти такую запись состоит в том, чтобы отсортировать список в порядке убывания; тогда запись с К-ым по величине значением окажется на К-ом месте. На это уйдет гораздо больше сил, чем необходимо: значения, меньшие искомого, нас, на самом деле, не интересуют. Может пригодиться следующий подход: мы находим наибольшее значение в списке и помещаем его в конец списка. Затем мы можем найти наибольшее значение в оставшейся части списка, исключая уже найденное. В результате мы получаем второе по величине значение списка, которое можно поместить на второе с конца место в списке. Повторив эту процедуру К раз, мы найдем К-ое по величине значение.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.