Сортировка одномерного массива методом пузырька

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

На занятии по физкультуре присутствовала 1 группа, состоящая из 5 студентов. Преподаватель по физкультуре в начале занятия должен их расставить по росту (т.е. – по его убыванию). Определим следующий алгоритм:

1. Преподаватель двигается вдоль шеренги слева направо.

2. Если левый студент в паре, ниже правого, преподаватель меняет их местами и переходит к следующей паре.

Рассмотрим в качестве примера массив

1

2

3

4

5

И разработаем алгоритм для обработки такого массива, тем более он подойдет и для массива, где ряд элементов уже стоит на своих местах

Для 5-ти элементов массива понадобилось четыре прохода (т.е. N-1). При этом номер левого элемента в пара от прохода к проходу менялся от 1 доN-K(где К –номер прохода). Исходя, из этого напишем текст процедуры сортировки массива по убыванию элементов:

(Имя файлa: Sort_Dec.pas)

Procedure Sort_Dec(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;

При этом предполагается, что число элементов массива N описано в программе как глобальная константа. Конечно, можно внутренний цикл завести до N-1, не связывая его с номером прохода, но тогда преподаватель обречен на лишнюю работу.

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

Примечание. Этот вид сортировки отличается от обменной тем, что за каждый проход большого цикла захватывается различное количество элементов массива, на каждом шаге более тяжелые опускаются на одну позицию вниз, а более легкие поднимаются на одну позицию вверх. Собственно тоже самое происходит и в обменной сортировке, но там на каждом шаге большого внешнего цикла обработке подвергается весь массив. Трудоемкость пузырьковой сортировки ограничена числом 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.

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