Реферат: Программирование различных типов задач

Type

arrType = Array[1 .. n] Of Integer;

Procedure Bubble(Var ar: arrType; n: integer);

Var i, j, T: Integer;

Begin

For i := 1 To n Do

For j := n DownTo i+1 Do

If ar[Pred(j)] > ar[j] Then Begin { < }

T := ar[Pred(j)]; ar[Pred(j)] := ar[j]; ar[j] := T

End

End;

Сложность этого метода сортировки составляет О(n^2)

Пузырьковая сортировка с просеиванием

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

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

const n = 10;

var

x: array[1 .. n] of integer;

i, j, t: integer;

flagsort: boolean;

procedure bubble_P;

begin

repeat

flagsort:=true;

for i:=1 to n-1 do

if not(x[i]<=x[i+1]) then begin

t:=x[i];

x[i]:=x[i+1];

x[i+1]:=t;

j:=i;

while (j>1)and not(x[j-1]<=x[j]) do begin
t:=x[j];
x[j]:=x[j-1];
x[j-1]:=t;
dec(j);
end;
flagsort:=false;
end;
until flagsort;
end;