Сортировка методом обмена

Определим тип массива:

const maxn=1000;

type size = 1..maxn;

vector=array[size] of integer;

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

procedure Data(var a:vector; var n:size);

var k:size;

begin

writeln(‘input n=?’); readln(n);

Randomize;

for k:=1 to n do a[k]:=random(100);

end;

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

Будем рассматривать упорядочение элементов массива по возрастанию. Простейший метод сортировки – это поочередное сравнивание двух соседних элемента массива, и если предшествующий элемент больше последующего a[j]>a[j+1], их меняют местами.

После первого прохода по всем элементам массива на последней n-позиции будет стоять максимальный элемент, после чего он исключается из обработки. Второй проход теперь организуется до (n-1)-го элемента и так далее. Сортировку обменом часто называют «пузырьковой» (bubble sort) по аналогии с процессом всплытия пузырька воздуха в жидкости.

Приведем один из вариантов такой процедуры:

procеdure BubbleSort(var a:vector; n:size);

var i,j:size;

begin

for i:=n downto 2 do

for j:=1 to i-1 do

if a[j]>a[j+1]

then Swap(a[j],a[j+1])

end;

Здесь Swap - процедура обмена элементами:

procedure Swap(var x,y:integer);

var z:integer;

begin

z:=x; x:=y; y:=z

end;

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

Необходимо выполнить отладку программы и провести упорядочение массива по возрастанию. Вычислить количество сравнений, которые осуществляются при сортировке массивов большой размерности (n>1000).

Скопировав процедуру пузырьковой сортировки и изменив знак сравнения соседних элементов, получим программу сортировки массива по убыванию. Вычислить количество сравнений, которые необходимо выполнить при переупорядочении элементов массива, т.е. наиболее трудоемкого процесса сортировки. Для этого проведите сначала сортировку по убыванию, а затем, используя этот массив на входе, проведите его сортировку по возрастанию.

Провести сортировку больших массивов вещественных чисел и символов, сделав соответствующие изменения в программе и проводя подсчет количества сравнений.