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

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

Типовые алгоритмы.

Алгоритмы последовательного поиска, двоичного поиска, сортировки относятся к циклическим (итеративным) структурам.

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

Сортировки методом простого выбора. Находят максимальный элемент в массиве из N элементов и меняют его местами с последним элементом (сортировка по возрастанию). Далее рассматривают массив без последнего элемента N-1. Общее количество сравнений пропорционально N².

Сортировка методом поплавка. Рассматривается весь массив и максимальный элемент постепенно перемещается на последнее место. Затем рассматривают массив из N-1 элементов. Общее количество сравнений пропорционально N².

Сортировка методом вставок. На i-м шаге считается, что первая часть массива, содержащая i-1 элемент, уже упорядочена. Далее берется i-й элемент, и для него подбирается j-е место в отсортированной части массива, такое, что упорядоченность не нарушается. i-й элемент помещается на это место, таким образом, что отсортированная часть массива увеличивается на один элемент. Общее количество сравнений пропорционально N².

Алгоритм последовательного поиска последовательно рассматривает элементы списка в том порядке, в котором они расположены в списке.Стоит задача найти в списке заданное значение. Алгоритм эффективен, когда имеют дело с короткими списками. Если список упорядочен, то поиск продолжают до тех пор, пока в списке есть имена и искомое имя больше, чем рассматриваемое на данном шаге имя списка. Если список неупорядочен, просматривают весь список. Общее количество сравнений пропорционально количеству элементов в списке N.

Алгоритм двоичного поиска. Если массив упорядочен, то тогда можно использовать алгоритм бинарного (двоичного) поиска. По результату сравнения искомого значения со средним элементом массива из рассмотрения исключают первую или вторую половину списка, в зависимости от того больше или меньше «средний» (находящийся в середине списка) элемент искомого элемента. Для поиска в оставшейся части списка его тоже разбивают на две части и процедура повторяется. Таким образом, метод состоит в последовательном разделении рассматриваемого списка на сегменты до тех пор, пока не будет найден искомый элемент или поле поиска не сузится до пустого сегмента. Общее количество сравнений пропорционально log₂N.

Алгоритм двоичного поиска реализуется с помощью рекурсивных структур. Цикл означает многократное выполнение набора команд. Рекурсия же предполагает повторное выполнение набора команд как подзадачу самой себя. При двоичном поиске для половины списка применяется та же процедура, что и для целого: список делится пополам и одна из частей отбрасывается.

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

Рекурсивные системы представляют собой циклические процессы и зависят от правильного управления ими. Их работа зависит от проверки условия завершения (для двоичного поиска – пустой список или найденное значение) и правильного их построения, которое обеспечивает выполнение этого условия завершения. [1, 10]

Дата добавления: 2014-10-31