Сортировка массива вставками. Поиск перебором

Сортировка массива вставками

Более быстрый и оптимальный метод сортировки - сортировка вставками.

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

Таким образом, алгоритм будет состоять из п-1-го прохода (n — размерность массива), каждый из которых будет включать четыре действия:

§ взятие очередного i-гo неотсортированного элемента и сохранение его в дополнительной переменной;

§ поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

§ сдвиг элементов массива от i-1-го до j-1-го вправо, чтобы освободить найденную позицию вставки;

§ вставка взятого элемента в найденную j-ю позицию.

Имейте в виду - первый индекс массива - 0.

program SortInsert;

uses Crt;

Const N=10;

var Arr : array[1..n] of Integer;

i, j, Temp : Integer;

begin

Clrscr; randomize;

Writeln ('Сортировка массива вставками’);

for i:=0 to n do

begin

arr[i]:=random(100);

write (arr[i]:3);

end;

for i := 1 to n do begin

Temp := Arr [i];

j := i - 1;

while Temp < Arr [j] do begin

Arr [j + 1] := Arr [j];

Dec (j);

if j < 0 then

Break;

end;

Arr [j + 1] := Temp;

end;

Writeln ('Sorted array');

for i:=0 to n do write (arr[i]:3);

readln;

end.

Поиск перебором

Чтобы найти какие-то данные в неупорядоченном массиве, применяется алгоритм простого перебора элементов. Следующая функция возвращает индекс заданного элемента массива. Её аргументы: массив с первым индексом 0, количество элементов в массиве и искомое число. Если число не найдено, возвращается -1.

function SearchPer (Arr : array of Integer; n, v : Integer) : Integer;

var

i : Integer;

begin

Result := -1;

for i := 1 to n do

if Arr [i] = v then begin

Result := i;

Exit;

end;

⇐ Предыдущая 123 Следующая ⇒