Сортировка массивов. Метод выбора. Двоичный поиск в массиве.

Под сортировкой понимают перестановку эл-тов массива в заданном порядке. Отсортировать числовую таблицу по возрастанию это значит переставить эл-ты так, чтобы они шли в порядке возрастания значений, при возрастании номеров эл-тов. Отсортировать символьную таблицу – это, значит, расположить эл-ты этой таблицы в алфавитном порядке. Любой метод сортировки оценивается по двум показателям:

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

2. число сравнений.

Сортировка выбора.

Пусть некоторая часть массива отсортирована, тогда, начиная с первого эл-та из неотсортированной части, находим в оставшейся части минимальный эл-т и меняем его местами с текущим эл-том. По окончанию просмотра всего массива он отсортирован. Изначально количество эл-тов из отсортированной части равно нулю.

Procedure vibor(n:byte; var a:mas1);

Var I,j,min:byte; vsp:integer;

Begin

For i:=0 to n-2 do begin

Min:=I;

For j:=i+1 to n-1 do

If a[j]<a[min] then min:=j;

Vsp:=a[i];

A[i]:=a[min];

A[min]:=vsp;

End;

End;

Поиск в массиве.

1. Линейный поиск. Если массив не отсортирован, то для того чтобы найти эл-т, обладающим заданным св-ом, нужно просмотреть весь массив. В этом случае кол-во действий пропорционально кол-ву эл-тов.

2. Двоичный поиск(применяется для отсортированных массивов). В массиве выбирается средний эл-т. Возможны 3 случая:

· Искомый эл-т больше чем средний, тогда поиск будет продолжен в правой части массива;

· Искомый эл-т меньше чем средний, тогда поиск будет продолжен в левой части массива;

· Искомый эл-т совпадает со средним, тогда поиск завершается.

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

L-левая часть, R-правая часть.

Procedure Dv_Poisk(n:integer; const a:mas1; x:integer; var k:integer);

Var L,R,C:integer;

Begin

L:=C; R:=n-1;

Repeat C:=(L+R) div 2;

If x>a[C] then L:=C+1

else if x<a[C] then R:=C-1;

until (a[C]=x) or (R<L);

if a[C]=x then k:=C

else k:=-1;

end;