Теоретическая работа ж. Сортировка массивов

Работая над программой для обслуживания соревнований, вы, должно быть, задумались о том, что было бы желательно расположить фамилии участников не произвольным образом, а упорядоченным. Причем для одних целей нам удобно упорядочить список по алфавиту, а для других - в порядке ухудшения результатов. Эту работу мы посвятим некоторым алгоритмам упорядочения (сортировки) массивов.

Итак, пусть у нас имеется числовой массив Mas, состоящий из N элементов. Требуется написать программу его упорядочения в возрастающем порядке, то есть чтобы по окончании работы программы выполнялось соотношение: Mas[1] < Mas[2] < ... < Mas[N] .

Самый понятный и естественный алгоритм, решающий эту задачу, - алгоритм прямого выбора. Он заключается в следующем:

• выбирается наименьший элемент и меняется местами с первым;

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

Вот как выполняется этот алгоритм на примере (см. схему на следующей странице; число элементов массива N=7).

Разобравшись в работе алгоритма, можно увидеть, что:

• независимо от начального расположения элементов алгоритм завершает работу всегда за N-1 проход;

• при каждом проходе совершается один обмен пары элементов;

• для нахождения минимального элемента требуется произвести при первом просмотре N-1 сравнение, при втором N-2 и т.д.

31	17	15	52	29	73	53	- исходный массив
15	17	31	52	29	73	53
15	17	31	52	29	73	53
15	17	29	52	31	73	53
15	17	29	31	52	73	53
15	17	29	31	52	73	53
15	17	29	31	52	53	73	- массив упорядочен

Таким образом, общее число обменов равно N-1, а общее число сравнений вычисляется по формуле:

.

Программа, реализующая этот алгоритм, выглядит так:

Program Sort1;

Const N = 5;

Var Mas : array[1..N] of Real;

Min : Real;

i,k,kmin : Integer;

begin

{ввод элементов массива}

...

{сортировка}

for i := 1 to N do {число просмотров = числу элементов}

begin

Min := Mas[i]; { считаем i-ый элемент минимальным }

kmin := i; { запоминаем номер мин. элемента }

for k := i to N do {поиск наименьшего из оставшихся}

if Mas[k] < Min then

begin Min := Mas[k]; kmin := k end;

Mas[kmin] := Mas[i]; { обмен наименьшего элемента }

Mas[i] := Min; { с первым из оставшихся }

end;

end.

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

На приведенной ниже схеме изображен процесс сортировки таким методом, причем первый просмотр изображен подробно, а при остальных просмотрах - только результат:

1-й просмотр:	31	17	15	52	29	73	53
	17	31	15	52	29	73	53
	17	15	31	52	29	73	53
	17	15	31	52	29	73	53
	17	15	31	29	52	73	53
	17	15	31	29	52	73	53
	17	15	31	29	52	53	73

2-й просмотр: 15 17 29 31 52 53 73

3-й просмотр: 15 17 29 31 52 53 73

При втором просмотре произошло два обмена, при третьем - ни одного, исполнение алгоритма закончилось.

В отличие от алгоритма прямого выбора число обменов и просмотров здесь существенно зависит от исходных данных. В самом худшем случае (массив упорядочен в обратном порядке) число обменов будет равно числу сравнений и составит . Если же массив почти упорядочен, то число обменов и сравнений существенно уменьшается. В частности, для отсортированного массива число обменов будет равно 0, а сравнений N-1. В этом и состоит преимущество "пузырькового алгоритма" перед алгоритмом прямого выбора.

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

Program Sort2;

Const N = 5;

Var Mas : array[1..N] of Real;

M : Real;

i,pr,last_N : Integer;

begin

{ввод значений элементов массива}

...

{сортировка методом пузырька}

pr := 1; { признак происшедшего обмена }

last_N := N; {номер последней просматриваемой записи}

while (pr = 1) and (last_N > 1) do

begin

pr := 0; { обмена еще не было, pr = 0 }

i := 1; { номер просматриваемой записи }

while i < last_N do

begin

if Mas[i] > Mas[i+1] then { нужно делать обмен }

begin

pr := 1; { обмен произошел, pr = 1 }

M := Mas[i];

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

Mas[i+1] := M;

end;

i := i+1;

end;

last_N := last_N-1;

end; end.