Студенты-Программеры

Program puzirek;
uses crt;
var
a:array[1..10] of integer;
i:integer;

Procedure sort;
var
i,j,k,rab:integer;
begin
for i:=1 to 10 do
for j:=1 to 10-i do
if a[j]>a[j+1] then
begin
rab:=a[j+1];
a[j+1]:=a[j];
a[j]:=rab;
writeln;
for k:=1 to 10 do
write(a[k],’.')
end;
end;

begin
clrscr;
randomize;
For i:=1 to 10 do
begin
a[i]:=random(5);
write(a[i]);write(’,');
end;
writeln;
sort;
readln;
end.

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

Массив определяется именем (идентификатором) и количеством размерностей (координат), необходимых для указания местонахождения требуемого элемента массива.

Алгоритм:

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

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

Программа, реализующая метод обмена («пузырька»), будет иметь следующий вид:

Program BubbleSort;

Uses Crt;

Const

N=20; {длина массива}

Type

TVector = array [1..n] of Real;

Var

Vector:TVector;

B : Real;

I, k : integer;

Begin

ClrScr;

Writeln (‘Введите элементы массива’);

For I: = 1 to n do Read (Vector[i]); Readln;

{——————————————————}

For k: =n downto 2 do

{“Всплывание”очередного максимального элемента}

{на k-ую позицию}

For I: = 1 to k-1 do

If Vector [i]>Vector [i+1] then

Begin

B: =Vector[i];

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

Vector [i+1]:=B

End;

{——————————————————}

Writeln (‘Отсортированный массив’);

For i: = 1 to n do Write (Vector[i]:8:2);

Writeln;

End.

Сравнение прямых методов сортировки.

Теоретические и практические исследования алгоритмов прямых методов сортировки показали, что как по числу сравнений, так и по числу присваиваний они имеют квадратичную зависимость от длины массива n. Исключение составляет метод выбора, который имеет число присваиваний порядка n*ln(n). Это свойство алгоритма выбора полезно использовать в задачах сортировки в сложных структурах данных, когда на одно сравнение выполняется большое число присваиваний. В таких задачах метод выбора успешно конкурирует с самыми быстрыми улучшенными методами сортировки.

Если сравнить рассмотренные прямые методы между собой, то в среднем методы вставки и выбора оказываются приблизительно эквивалентными и в несколько раз (в зависимости от длины массива) лучше, чем метод обмена («пузырька»).