Прз на эвм(3) Сортировка и поиск

Сортировка - это процесс перегруппировки заданного множества объектов в некотором определенном порядке.

Цель сортировки: облегчить поиск элементов.

Методы сортировки можно разбить на два класса – сортировку массивов и сортировку файлов.

СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВКЛЮЧЕНИЯ.

Алгоритм: элементы массива мысленно делятся на уже "готовую" и исходную последовательности. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется на нужное место.

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

Процесс просеивания может закончиться при выполнении одного из двух условий:

• найден элемент a_j с ключом, меньшим чем ключ у х;

• достигнут левый конец готовой последовательности.

СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ВЫБОРА

Алгоритм:

• выбирается элемент с наименьшим ключом;

• он меняется местами с первым элементом a₁;

• затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.

СОРТИРОВКА С ПОМОЩЬЮ ПРЯМОГО ОБМЕНА

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

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

Пусть имеется одномерный массив Х: Р, содержащий N целых чисел. В таких условиях з/ча поиска состоит в том, что треб-ся отыскать эл-нт массива, знач.которого совпадает с зад-ым знач.ключа Z:integer.

Метод перебора: просмотр элементов от начала массива к его концу

Условия:

1. элемент массива счи-ся найденным, е/и опред-но 1≤k≤N, для которого Х[k]=Z

2. т.к. эл-нт массива с нулевым идексом не сод-ит полезн.инф-ции, то рез-ат поиска к=0 считается признаком неудачного поиска

3. поиск д.б.прекращен немедленно, е/и нужный эл-нт массива найден

4. е/и заверщен просмотр всех N эл-тов массива, но нужный не найден, то поиск прекращается

пример( метод перебора)

Procedure MP(Z:integer;N:byte; Var X:P; Var k:byte);

Var j:byte;

Begin k:=0;j:=1;

While j<=N do

If X[j]=Z then begin k:=j; j:=N+1 end

Else j:=j+1

End;

Метод деления отрезка пополам

1. обозначим концы отрезка А=1 и к=N+1

2. находим порядковый номер S эл-та, распол-го в середине массива по формуле S=(A+k)div2

3. e/и эл-нт массива Х[S] оказ-ся < Z, то искомое место вставки м.находиться только дальше порядкового номера S , поэтому А=S+1

4. иначе принимаем к=S

5. новые знач.концов испол-ем для нахожд-ия новой середины и т.д.

пример( метод дел.отр.пополам)

Procedure DP(Z:integer;N:byte; Var X:P; Var k:byte);

Var A,S:byte;

Begin A:=1;k:=N+1;

While A<k do begin S:=(A+k)div2

If X[S]<Z then A:=S+1

Else k:==S

End;

End;

,Пример(прямой обмен):

uses crt;

const n=100;

var a : array[1..n] of integer;

i,x : integer;

p : boolean;

procedure init;

begin randomize; for i:=1 to n do a[i]:=random(100); end;

procedure output;

begin for i:=1 to n do write(a[i]:5); writeln; end;

BEGIN

clrscr; init; writeln;writeln('Исходный массив:'); output;

{сортировка пузырьком}

repeat p:=false;

for i:=n-1 downto 1 do if a[i]>a[i+1] then

begin x:=a[i]:a[i]:=a[i+1];a[i+1]:=x; p:=true; end;

until p=false;

writeln;writeln('Отсортированный массив:'); output;readln;

END.