Имя фала: Sort_Inc.pas

Имя фала: FastSort.pas

Чем отличаются две программы?

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

Примечание. Этот вид сортировки отличается от обменной тем, что за каждый проход большого цикла захватывается различное количество элементов массива, на каждом шаге более тяжелые опускаются на одну позицию вниз, а более легкие поднимаются на одну позицию вверх. Собственно тоже самое происходит и в обменной сортировке, но там на каждом шаге большого внешнего цикла обработке подвергается весь массив. Трудоемкость пузырьковой сортировки ограничена числом N*(N-1)/2. Пузырьковая сортировка обладает свойством устойчивости.

Program Z;

uses crt;

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

i,j,n,c:integer;

begin

clrscr;

write('количество элементов массива ');

read(n);

for i:=1 to n do read(a[i]);

for i:=n-1 downto 1 do

for j:=1 to i do if a[j]>a[j+1] then begin c:=a[j];

a[j]:=a[j+1];a[j+1]:=c;

end;

for i:=1 to n do write(a[i],' ');

end.

Пример. Сортировка обменом по возрастанию массива a из n целых чисел.

Рrogram Sort_Obmen;

var а:array[1..100] of integer;

n,i,k,x : integer;

begin write('количество элементов массива ');

read(n);

for i:=1 to n do read([i]);

for k:=n-1 downto 1 do {количество сравниваемых пар}

for i:=1 to k do if a[i]>a[i+1] then {меняем местами соседние элементы}

begin

x:=a[i];

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

a[i+1]:=x;

end;

for i:=1 to n do write(a[i],' '); {упорядоченный массив}

end.

Наряду с сортировкой методом пузырька, существуют и некоторые другие, более эффективные методы сортировки: быстрая сортировка, метод Шелла, сортировка вставками... Однако рассмотренный алгоритм наиболее прост в реализации и логичен.

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

Procedure FastSort(Var aa:Massive);

Var ii,kk,nn:byte;

Begin

nn:=n;

Repeat

For ii:=1 to nn-1 Do Begin

kk:=0

If (aa[ii]>aa[ii+1]) Then Begin

Swap (aa[ii],a[ii+1]);

Inc(kk);

End;

End;

Dec(nn);

Until (kk=0);

End;

В то время, как при сортировке предыдущем методом для массива из 10 элементов понадобится 9 проходов, для данного алгоритма это число может уменьшиться. К примеру, массив из значений (1,-3,7,-10,11,4,-6,2,5,-4) будет отсортирован за 8 проходов, а массив (1,4,3,2,4,5,6,7,10,11) – всего за 1.

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

Procedure Sort_Inc(Var aa:Massive);

Var ii,kk:byte;

Begin

For kk:=1 to n-1 Do Begin

For ii:=1 to n-kk Do Begin

If (aa[ii]>aa[ii+1]) Then Begin

Swap (aa[ii],a[ii+1]);

End;

End;

End;

End;