Бинарный поиск в упорядоченных массивах

Метод быстрой сортировки с разделением

Сортировка методом пузырька.

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

Текст программы сортировки массива по невозрастанию можно записать в таком варианте:

program Sort_Puz; (Сортировка массива ″пузырьковым″ методом по невозрастанию}

const

Count=20;

M: array [1.. Count] of

byte=(9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5);

var I, J, N, L: Byte;

A:integer;

begin

Writeln(′Исходный массив:′);

for I:=1 to Count do Write (M [I]′,’);

Writeln;

A:=0;

for I:=2 to Count do(Сортировка ″пузырьковым″ методом по невозрастанию}

begin

for J:= Count downto Ido

begin

A:=A+1;

if M[J-1]<M[J] then {Если элемент справа больше элемента слева, то ″вытеснить″ его влево - пузырек ″всплывает″}

begin

K: = M [J-1]; {Обмен значениями этих элементов}

M [J-1]: = M [J];

M [J]: = K;

{Печатать текущее состояние массива после каждой перестановки}

for L:=1 to Count do Write (Writein (′Число итераций=′,А);

end;

end;

end;{Завершение сортировки}

end.

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

Program Quck_sort; {Быстрая сортировка по невозрастанию дроблением массива на части}

uses Crt;

const

Count=20;

M: array [1.. Count] of byte=(9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);

var

I, A: integers;

procedure QuickS(First, Last: integer);

var I,J,X,W,L: integer;

begin

I: = First; {Левая граница массива - первый элемент}

J: = Last; (Правая граница массива - первый элемент}

X: =M [(First+ Last) div 2]; (Определить середину массива}

repeat

while M[I]>X do

I: =1+1;

While X>M [J] do

J: = J-1;

A: =A+1;(Увеличить число итераций обмена элементов}

if K=J then

begin (Обменять местами элементы}

W: =M[i];

M [I]:=M [J];

M [J]:=W;

I: =I+1;

J: =J-1;(Печатать текущее состояние массива после каждой перестановки}

for L:=1 to Count do Write (‘’, M [L]);

Writeln (′Число итераций =′, А);

end;

until I>J;

if First<J then QuickS (First, J)

if K Last then Quacks(I, Last); {Рекурсивный вызов процедуры QuickS }

end;{Конец сортировки}

begin {Начало основной программы}

CIrScr;

Writeln (′Исходный массив:′);

Writeln;

for I:=1 to Count do Write(M[I]:3,′‘); Writeln;

A: =0;

QuickS (1, Count);{ Вызов процедуры сортировки QuickS}

Writeln {′Отсортированный массив:′); Writeln;

for I:=1 to Count do Write(M[I]:3,′‘); Writeln;

end.

После первого вызова процедуры QuickS в исходном массиве: 9 11 12 3 1 9 1 5 1710 183 1 9 17 9 12 20 20 19 2 5 будет определена его середина (10-й элемент) и переменной X присвоено значение M[10], т.е. 18. После этого массив делится на две части: 9 1 12 3 1 9 1 5 17 10 18 и 3 19 17 9 12 20 20 9 2 5

Далее выполняется обмен элементами по следующему правилу:

При просмотре левой части массива слева направо выполняется поиск такого элемента массива, что M[I]>X, затем при просмотре правой части справа налево отыскивается такой элемент, M[I]<X. Выполняется обмен местами данных элементов, пока все элементы слева от середины, удовлетворяющие условию M[I]>X, не будут обменены с элементами, расположенными справа от середины и удовлетворяющими условию M[I]<X. В результате этого получим массив из двух частей следующего вида:

9 11 12 19 1 5 17 10 18 3 19 17 9 12 20 20 19 2 5 Число итераций=1

19 20 12 3 19 1 5 17 10 18 3 19 17 9 12 20 11 9 2 5 Число итераций=2

19 20 20 3 19 1 5 17 10 18 3 19 17 9 12 12 11 9 2 5 Число итераций=3

19 20 20 19 19 1 5 17 10 18 3 3 17 9 12 12 11 9 2 5 Число итераций=4

19 20 20 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=5

Далее рекурсивно левая часть в свою очередь дробится на две части, и вызывается процедура для сортировки левой части (с 1-го по 6-и элемет)

20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=7

20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=8

После того как левая часть массива отсортирована, опять рекурсивно вызывается процедура, в которой определяется середина данной части массива, и выполняется обмен элементов. Массив становится таким:

20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=9

20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=10

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

Затем рекурсивно вызывается процедура для аналогичной сортировки правой части (с 7-го по 19-й элемент). Результат последовательных этапов сортировки массива отображается так:

20 20 19 19 19 18 5 17 10 1 3 3 17 9 12 12 11 9 2 5 Число итераций=11

20 20 19 19 19 18 17 17 10 1 3 3 5 9 12 12 11 9 2 5 Число итераций=12

20 20 19 19 19 18 17 17 10 1 3 3 5 9 12 12 11 9 2 5 Число итераций=13

20 20 19 19 19 18 17 17 10 9 3 3 5 9 12 12 11 1 2 5 Число итераций=14

20 20 19 19 19 18 17 17 10 9 1 1 3 5 9 12 12 3 1 2 5 Число итераций=15

20 20 19 19 19 18 17 17 10 9 1 1 12 5 9 12 3 3 1 2 5 Число итераций=16

20 20 19 19 19 18 17 17 10 9 1 1 12 12 9 5 3 3 1 2 5 Число итераций=17

20 20 19 19 19 18 17 17 10 9 1 1 12 12 9 5 3 3 1 2 5 Число итераций=18

20 20 19 19 19 18 17 17 12 9 1 1 12 10 9 5 3 3 1 2 5 Число итераций=19

20 20 19 19 19 18 17 17 12 12 1 1 9 10 9 5 3 3 1 2 5 Число итераций=20

20 20 19 19 19 18 17 17 12 12 1 1 9 10 9 5 3 3 1 2 5 Число итераций=21

20 20 19 19 19 18 17 17 12 12 1 1 9 10 9 5 3 3 1 2 5 Число итераций=22

20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 3 3 1 2 5 Число итераций=23

20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 3 3 1 2 5 Число итераций=24

20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 3 3 1 2 5 Число итераций=25

20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 3 3 1 2 5 Число итераций=26

20 20 19 19 19 18 17 17 12 12 1 1 10 9 9 5 5 3 3 2 1 Число итераций=27

По последнему значению А определяем что для данного массива сортировка по невозрастанию выполняется за 27 итераций.

Как видно из приведенных примеров, алгоритм ″быстро″ сортировки дает лучшие результаты, чем пузырьковый метод, однако следует учесть, что в некоторых случаях это преимущество снижается. Например, если применить эту программу для сортировки массива M, элементы которого имеют значение 29, 27, 24, 3, 23, 19, 19, 18, 1, 17, 15, 13, 1, 0, 9, 9, 8, 6, 6, 5, то сортировка будет выполнена за 28 итераций, т.е. время процесса и число итераций даже увеличатся, несмотря на то, что исходный массив в большей степени упорядочен, в то время как сортировка линейным методом-190 итераций для обоих массивов, пузырьковым-166(для первого массива-170).

Едва ли не самой внушительной демонстрацией эффективности применения компьютеров являются задачи, в которых осуществляется поиск информации в некотором списке. Ранее мы использовали метод линейного (последовательного) поиска, суть которого заключается в последовательном просмотре всего списка элементов массива и сравнении значения очередного элемента с заданным для поиска. Этот метод поиска вполне эффективен на неупорядоченных массивах данных, а на предварительно отсортированных массивах значительно эффективнее выполнять поиск другими методами. Например, метод линейного поиска практически бесполезен при поиске информации в массивах большого размера, так как занимает много времени.

Один из эффективных метод поиска в больших отсортированных массивах является бинарный поиск, или поиск методом деления пополам. В основе этого метода лежит идея целенаправленных последовательных догадок о предполагаемом местоположении искомого элемента. Такой метод можно проиллюстрировать на пример шуточного совета, как поймать в Африке льва: ″Для начала разделим Африку пополам. Ясно, что лев находится только в одной половине. Та половина, в которой находится лев, снова делится пополам и т.д. Площадь Африки приблизительно 30 млн. км². Следовательно, после примерно 45 делений мы получим площадку, не превышающую 1 м². Теперь на такой площадке льва поймать нетрудно″.

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

Составим программу, которая выполняет бинарный поиск заданного элемента в отсортированном массиве целых чисел, элементы которого имеют значения:

20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1.

Введем в разделе описания констант размер массива Count=20 и опишем массив целых чисел:

M: array [1.. Count] of byte=20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1.).

В разделе описания переменных опишем следующие переменные:

N-для хранения значения искомого элемента;

I-для указания очередного элемента массива;

First-указание индекса элемента - левой границы рассматриваемой части

массива;

Last-указание индекса элемента - правой границы рассматриваемой части

массива;

Found-логическая переменная, в которой будет записываться результат

поиска;

A-переменная, значение которой будет равно числу перестановок элементов.

В начале программы запишем вывод исходного массива на экран, затем вывод запроса искомого элемента, после чего считывание его значения в переменную N.

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

A: =0;

First: =1;

Last: = Count;

Found: =False;

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

I: = (First+ Last) div 2

Условие поиска запишем оператором

if M[I]=N then Fond: = True

Если условие M[I]=N выполняется, то искомый элемент найден, переменной Found присваивается значение True, и управление передается за пределы оператора if. Если это условие не выполняется, то оператором

if M[I]>N then First: =I+1 else Last: =I-1;

проверяется условие M[I]>N. Если оно выполняется, значит значение искомого элемента расположено в правой части массива, поэтому левую границу части массива переносим в позицию I+1 (First: =I+1), иначе элемент нужно искать в левой части массива, а, значит правую границу части массива переносим в позицию I-1 (Last: =I-1). Затем нужно записать увеличение счетчика повторений при поиске A: =А+1. оператор повтора завершим записью условия окончания (Found) or (first>Last). Если это условие выполнится, т.е. если найдется искомый элемент или будет просмотрен весь массив, цикл завершится. Этот фрагмент программы можно записать так:

repeat

I: = (First+ Last) div 2;

if M[I]=N then Fond: = True

else

begin

if M[I]>N then First: =I+1;

else Last: =I-1;

end;

A: =А+1;

until (Found) or (First>Last);

{Повторить поиск}

{Разделить на две части}

{Искать элемент в правой части}

{Искать элемент в левой части}

{Увеличить счетчик числа итераций}

{Завершить, если найдется искомый элемент или будет просмотрен весь массив}

В заключительной части программы запишем условие вывода результата поиска. Если значение переменной Fond= True, то выведем на экран сообщение о том, какую позицию в массиве занимает искомый элемент, иначе выведем сообщение о том, что такого элемента в массиве нет. После чего выведем сообщение о том, сколько просмотров массива выполнялось в процессе поиска.

В целом текст программы будет записан следующим образом:

program Find Bin;

const

Count=s 20;

M: array [1.. Count] of byte=20,20,19,19,19,18,17,17,12,12,11,10,9,9,5,5,3,3,2,1.).

var

N, I, First, Last Byte;

A: integer;

Fond: boolean;

Begin

Writeln (′Исходный массив:′);

for I:=1 to Count do Write(M[I]:3,′′);

Writeln;

Writeln;

Write(′Введите значение элемента массива для поиска>′);

Readln (N);

A: =0;

First: =1;

Last: = Count;

Found: =False; {Элемент не найден}

Repeat {Повторить поиск}

I: = (First+ Last) div 2;{Разделить на две части}

if M[I]=N then Fond: = True else

begin

if M[I]>N then First: =I+1{Искать элемент в правой части}

else Last: =I-1;{Искать элемент в левой части}

end;

A: =А+1; (Увеличить счетчик числа итераций)

until (Found) or (First>Last);(Завершить, если найдется искомый элемент или будет просмотрен весь массив}

if Found then Writeln(′Искомый элемент′,N,′в массиве занимает′,I,′-ю позицию′) else Writeln (′В массиве нет искомого элемента′,N);

Writeln (′Поиск выполнен за′, А, ′итераций′);

end.

Запустите интегрированную среду программирования. Введите текст программы Find_Bin и запишите файл на диск под соответствующим именем, а затем откомпилируйте его. После того как компиляция выполнится успешно, запустите программу на исполнение в пошаговом режиме и наблюдайте изменения текущих значений переменных First, Last, I, M[I], а также значение выражений M[I]>N и (Found) or (First>Last). Обратите внимание на то, что бинарный поиск в сортированных массивах выполняется за небольшое число итераций.

Контрольные вопросы.

1. Для чего используется сортировка?

2. В чём состоит метод быстрой сортировки с разделением?

3. В чём суть сортировки методом пузырька?

4. Как происходит линейная сортировка (сортировка отбором)?

5. Как осуществляется бинарный поиск в упорядоченных массивах?

Дата добавления: 2014-01-06