Алгоритмы сортировки массивов: метод выбора, метод вставки, метод быстрой сортировки Хоара, метод Шелла. Поиск в массиве (стр. 4 )

Чаще всего подход «разделяй и властвуй» используют из-за того, что он обеспечивает более быстрые решения, чем простые итерационные алгоритмы.

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

Он явно и немедленно отыскивает максимальный элемент массива, размер которого равен 1.

Для N>1 код разделяет массив на два, размер каждого из которых меньше N, исходя из индуктивного предположения, находит макс. эл-ты в обеих частях и возвращает большее из этих двух значений, которое должно быть максимальным значением для всего массива.

Лемма Рекурсивная функция, которая разделяет задачу размерности N на две независимые (непустые) решающие ее части, рекурсивно вызывает себя менее N раз.

Лемма. Бинарный поиск исследует не более lgN +1 чисел.

Бинарный поиск позволяет решить большую задачу с 1 миллионом чисел при помощи 20 сравнений.

Нерекурсивный алгоритм двоичного поиска.

Начало

       Установить левую границу поиска =1;

       Установить правую границу поиска =N;

       Пока левая граница <= правой

               Нц

               Найти середину области поиска m:=(l+r)/2;

               Если искомое число <а[m], то  изменить правую границу R:=m-1;

               Если искомое число >а[m], то изменить левую границу L:=m+1;

               Если искомое число =а[m], то искомое число найдено.

               Кц

       Сообщить, что искомого числа в массиве нет.

Рекурсивный алгоритм двоичного поиска.

Алгоритм Двоичный поиск (l, r)

Начало

       Если левая граница <= правой, то

               Нц

               Найти середину области поиска m:=(l+r)/2;

               Если искомое число <а[m], то  Двоичный поиск (l, m-1);

               Если искомое число >а[m], то Двоичный поиск (m+1,r)

               Если искомое число =а[m], то искомое число найдено.

               Кц

       Иначе Сообщить, что искомого числа в массиве нет.

Применение алгоритма «разделяй и властвуй» для отыскания максимального из N элементов массива а[1..n]. Не рекурсивный алгоритм решает задачу за один проход. Используемые обозначения:L– левая граница, R-правая граница, M-средний элемент.

Рекурсивный алгоритм нахождения макс. элемента.

Алгоритм  Макс (а, l,r)

Начало

       Если левая граница <= правой, то

               Нц

               Найти середину области поиска m:=(l+r)/2;

               U:= Макс (а, l,m);

               V:= Макс (а, m+1,r)

               Если u>v то Макс:= u, иначе Макс:= v

               Кц

Многие алгоритмы типа «разделяй и властвуй» имеют одинаковую рекурсивную структуру: CN = 2*CN/2 + N, где N>=2 и C1 =0.

Некоторые алгоритмы типа «разделяй и властвуй» могут выполнять различный объем вычислений для различных вызовов функций, время выполнения таких алгоритмов зависит от конкретного способа разделения на части. В случае, когда задача делится пополам, а затем  алгоритм работает только с одной половиной (сумма размеров частей равна общей размерности) – время выполнения линейно связано с количеством вызовов. Другие алгоритмы типа «разделяй и властвуй» могут разделять задачу  на части, сумма размеров которых меньше или больше размерности всей задачи. Эти алгоритмы все же относятся к алгоритмам типа «разделяй и властвуй», поскольку каждая часть меньше целого, но анализировать их труднее.

Бинарный поиск элемента, равного у в упорядоченном массиве

Оператор цикла «Пока»

L:=1;

R:=n;

Found:=false;

Result:=-1;

       While (l<=r) и not found

       do

       начало

                       Mid:=round((l+r)/2);

               Если a[mid]=y

               то начало result:=mid; found:=true конец

               иначе

                               Если y<a[mid]

                               то  r:=Mid-1

                               иначе  l:=Mid+1;

       конец;

       Если found

       то  Write(' Search digit found in massiv at number ',result)

       иначе Write(' Search digit not found in massiv ');

Оператор цикла «Повторять»

l:=1;

r:=n;

Found:=false;

Result:=-1;

       Повторять

               Mid:=trunc(((l-r)/2)+r);

               Если a[mid]=y

                       то

начало

found:=true;

result:=mid;

конец

                       иначе

                               Если y<a[mid]

                               то  r:=Mid-1

                               иначе  l:=Mid+1;

       До (l>r) or found;

       Если found

       то        Write(' Search digit found in massiv at number ',result)

       иначе        Write(' Search digit not found in massiv ');

Рекурсивный алгоритм

Алгоритм BS

Входl, r int;

Выход a:tarray; number int; flag:char;

Локальные переменные m int;

начало

Если l<=r то

начало

               m:=round((r+l)/ 2) ;

               Если x=a[m]

               то

                       начало

                               number:=m;

                               flag:=true;

                       конец;

               Если x<a[m]

                       то Bs(l, m-1,number, flag)

                       иначе Bs(m+1,r, number, flag)

конец;

конец;

BS(1,8,number, flag);

Если flag то

Write(' Search element ',number)

иначе Вывод (' El not found');