Алгоритмический язык Паскаль (стр. 21 из 31)

1. Массив уже отсортирован (но мы не знаем об этом).

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

2. Исходный массив упорядочен по убыванию.

Здесь самым лучшим методом является прямой выбор, т.к. вся работа будет проделана за половину ходов (проход до середины):

ПРИМЕР:

1 шаг:	8	6	4	2	0	2 шаг:		0	6	4	2	8
Результат:			0	2	4	6	8

3. Массив дан случайным образом.

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

13.5 Улучшенный метод сортировки. QUICK – сортировка

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

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

Эта идея приводит к тому, что нужно построить процедуру, которая допускает обращение самой к себе, т.е. рекурсивную процедуру, имеющую входными параметрами номера элеметов:

1-ый - левый элемент: L,

2-ой - правый элемент: R.

На начало процедуры эти параметры должны получить значения:

L = 1; R = N.

В процедуре используется цикл REPEAT по сближению левой и правой границ.

procedure QUICKSORT (L, R: integer; var M: MAS);

var I,J,W,X: integer;

begin

¦ {Установка границ, от которых идет движение к середине}

¦ I:= L; J:= R;

¦ {Выбор граничного элемента}

X:= M[(L+R) div 2];

¦ repeat

¦ ¦ { Поиск слева элемента, большего X }

¦ ¦ while X > M[I] do I:= I+1;

¦ ¦ { Поиск справа элемента, меньшего X }

¦ ¦ while X < M[J] do J:= J-1;

¦ ¦ if I <= J then

¦ ¦ begin

¦ ¦ ¦ W:= M[I]; {Обменместами

¦ ¦ ¦ M[I]:= M[J]; I-гои J-го

¦ ¦ ¦ M[J]:= W; элементов,

¦ ¦ ¦ I:=I+1; дальнейшее продвижение

¦ ¦ ¦ J:=J-1; вперед (назад)}

¦ ¦ end;

¦ ¦ {Выход из цикла, если левый край перевалил за правый}

¦ until I > J;

¦ { Повтор обмена для левой части }

¦ if L < J then QUICKSORT (L,J,M);

¦ { Повтор обмена для правой части }

¦ if R > i then QUICKSORT (I,R,M);

¦

end;

ПОЯСНЕНИE. Рассмотрим работу этой процедуры на примере сортировки следующего массива:

6	4	3	2	7	1	5
1	2	3	4	5	6	7

Здесь имеем значения L=1; I=1; J=7; R=7. Цикл WHILE X > M[I] при Х = 2 дает сразу же отказ и значение I остается старым, т.е. I = 1. Цикл WHILE X < M[J] при Х = 2 дает J = 6. Сравнение IF I <= J дает 1 <= 6, т.е. истина, отсюда идет обмен между I-м и J-м элементами - первый элемент 6 меняется местом с шестым элементом 1:

1	2	3	4	7	6	5
1	2	3	4	5	6	7

и индекс I (J) увеличивается (уменьшается):

I:=I+1, т.е. I = 2;

J:=J-1, т.е. J = 5.

Сравнение I > J, т.е. 2 > 5, является ложным, поэтому идет возврат наверх. Циклы WHILE доводят значения переменной I до 2, а значение J становится равным 4. Так как I=2 <= J=4, то идет обмен между 2-м и 4-м элементами:

1	2	3	4	5	6	7
1	2	3	4	5	6	7

и индексы получают значения: I = 3, J = 3.

При таких значениях индексов имеем M[I]=M[J]=3, что в результате работы циклов WHILE дает I=3 и J=2. Сравнение I<=J будет ложным, поэтому обмена элементов нет, кроме того, становится истинным условие проверки окончания работы цикла REPEATE (I>J) и происходит переход на рекурсивное обращение к самой процедуре.

Из двух условий истинным является первое (сравнение L < J дает 1< 2), поэтому идет обращение к процедуре при параметрах L=1 и R=2. Однако для этих праметров упорядочивание уже произошло. Затем формируется отрезок [3,7], где происходит обмен между 5-м и 7-м элементами:

1	2	3	4	5	6	7
1	2	3	4	5	6	7

В результате этой работы массив уже упорядочен, однако затем формируются отрезки [3,6] и [5,6], при которых никаких обменов не происходит, но параметры I, J получают значения: I=6, J=4. Ни одно из сравнений L<J (5<4) и R>I (6>6) не является истинным, поэтому рекурсия завершается и процедура заканчивает свою работу.

ЗАМЕЧАНИЕ. Данная процедура очень медленно обрабатывает уже упорядоченный массив.

14. СТРУКТУРЫ ПОСЛЕДОВАТЕЛЬНОГО ДОСТУПА. ЛИНЕЙНЫЕ СПИСКИ

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

Итак, рассмотрим теперь более подробно эти виды динамических структур.

14.1 Очередь

Очередь - это линейный список, в котором все включения производятся на одном конце списка, а все исключения (и обычно всякий доступ) - на другом. Очередь иногда называют циклической памятью или списком типа FIFO (от первых букв английской фразы "First Input First Output"): первым включается - первым исключается.

При работе с очередью мы говорим о ее начале и конце – объекты вставляются в конце очереди и удаляются в начале:

ИСКЛЮЧИТЬ			ВКЛЮЧИТЬ
	*	®	*	®	*	®	*
НАЧАЛО		ВТОРОЙ		ТРЕТИЙ		КОНЕЦ

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

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

type SS = ^ZVENO;

ZVENO = record

elem: integer;

next: SS;

end.

Рассмотрим сначала алгоритм формирования очереди. Для этого введем три указателя - на начало очереди, на ее конец и текущий указатель:

VAR L: SS; {начало очереди}

R: SS; {конец очереди}

K: SS; {рабочий указатель}

el1,el2: integer;{рабочие элементы}

Алгоритм формирования очереди представлен на следующей схеме:

ОПЕРАТОРЫ	ПОЯСНЕНИЕ
new(K);
el:=random(10);	K	*	el	nil
K^.next:=nil;
K^.elem:=el;
L:=K;	L	*
	K	*	el	nil
R:=K;	R	*
el:=random(10);
while el<>0
do begin	K	*	el	nil
new(K);
K^.elem:=el;
K^.next:=nil;
	L	*	el	*
R^.next:=K;
	R	*	K	el	nil
R:=K;	L	*	el	*
	R	*	el	nil
el:=random(10); end;	K

Запишем теперь полностью процедуру формирования очереди:

procedure FORMIR_OTCHERED_1 (var L, R: SS);

var K: SS; EL: integer;

begin

¦ { Формирование первого звена очереди }

¦ randomize; EL:= random(10);

¦ new(K); L:= K; R:= K;

¦ K^.elem:= EL; K^.next:= nil;

¦ EL:= random(10);

¦ { Помещение очередного элемента в очередь }

¦ while EL <> 0 do

¦ begin

¦ ¦ new(K);