Алгоритмический язык Паскаль
13.2 Прямой выбор
Суть метода состоит в том, что среди всех элементов массива выбирается наименьший и ставится на первое место, а элемент, занимавший первое место, перемещается на место наименьшего. Затем среди оставшихся элементов от второго до N-го проводится та же операция, а именно: среди элементов массива от второго до N-го выбирается наименьший и перемещается на второе место, а элемент, стоящий на втором месте, занимает место наименьшего.
Эта идея реализуется в виде вложенных циклов: внешний - по I от 1 до N-1; внутренний - по J от I+1 до N.
ОБЩАЯ СХЕМА ПРОГРАММЫ:
for I:=1 to N-1 do
begin
¦ {Запоминание индекса и самого I-го элемента}
¦ for J:=I+1 to N do
¦ begin
¦ {Поиск минимального элемента от I+1 до N}
¦ end;
¦ {Перестановка I-го и минимального элементов}
end.
ОБЩИЙ ВИД ПРОГРАММЫ:
procedure SELECTION (var MM:MAS);
var I,J,K,X: integer;
begin
¦ for I:= 1 to N-1 do
¦ begin
¦ ¦ { Это тело внешнего цикла }
¦ ¦ K:= I; X:= MM[I];
¦ ¦ { Внутренний цикл - поиск MIN элемента }
¦ ¦ for J:= I+1 to N do
¦ ¦ if X > MM[J] then
¦ ¦ begin
¦ ¦ ¦ { Запоминание номера и значения
¦ ¦ ¦ минимального элемента }
¦ ¦ ¦ X:= MM[J];
¦ ¦ ¦ K:= J;
¦ ¦ end;
¦ ¦ { Минимальный и I-й элементы меняются местами}
¦ ¦ MM[K]:= MM[I]; MM[I]:= X;
¦ end;
end.
Проследим работу этой программы на следующем примере:
I=0
| -3 | 2 | 4 | 1 | 6 | 3 |
® исходный массив
I=1
| -3 | 2 | 4 | 1 | 6 | 3 |
® 1-й шаг: ничего не происходит, т.к. минимальный элемент на своем месте
I=2
| -3 | 1 | 4 | 2 | 6 | 3 |
® 2-й шаг: 2-й и 4-й поменялись местами
I=3
| -3 | 1 | 2 | 4 | 6 | 3 |
® 3-й шаг: 3-й и 4-й поменялись местами
I=4
| -3 | 1 | 2 | 3 | 6 | 4 |
® 4-й шаг: 4-й и 6-й поменялись местами
I=5
| -3 | 1 | 2 | 3 | 4 | 6 |
® 5-й шаг: 5-й и 6-й поменялись местами
Всего N-1=5 шагов. Часть из них результативна (2,3,4,5), а первый шаг никаких перестановок не производит. Отметим, однако, что даже при нерезультативных ходах все циклы работают до конца и за время сортировки внутренний цикл выполнится N(N-1)/2 раз.
13.3 Прямой обмен (метод пузырька, всплытие)
Суть его заключается в том, что в отличие от первых двух методов, где просмотр массива шел по увеличению индекса I, т.е. от начала массива к концу, здесь производится проход от конца массива к началу до I-го элемента, и каждый раз, если А[J-1] > А[J], они меняются местами.
В этом методе также есть два вложенных цикла: внешний цикл поидет от 2 до N, а внутренний по J - от N до I:
for I:= 2 to N do
for J:= N downto I do
{ Обмен местами (всплытие) более легкого элемента }
end;
end.
ОБЩИЙ ВИД ПРОГРАММЫ:
procedure BUBLESORT (var MM: MAS);
var I,J,X: integer;
begin
¦ for I:=2 to N do
¦ for J:= N downto I do
¦ if MM[J-1] > MM[J] then
¦ begin
¦ ¦ X:= MM[J-1];
¦ ¦ MM[J-1]:= MM[J];
¦ ¦ MM[J]:= X
end;
end.
Работу программы иллюстрирует пример с тем же исходным массивом, что и ранее:
| I=2 | I=3 | ||||||||||||||
| J=6 | -3 | 2 | 4 | 1 | 3 | 6 | J=6 | -3 | 1 | 2 | 4 | 3 | 6 | ||
| J=5 | -3 | 2 | 4 | 1 | 3 | 6 | J=5 | -3 | 1 | 2 | 3 | 4 | 6 | ||
| J=4 | -3 | 2 | 1 | 4 | 3 | 6 | J=4 | -3 | 1 | 2 | 3 | 4 | 6 | ||
| J=3 | -3 | 1 | 2 | 4 | 3 | 6 | J=3 | -3 | 1 | 2 | 3 | 4 | 6 | ||
| J=2 | -3 | 1 | 2 | 4 | 3 | 6 |
Все остальные обработки при I = 4, 5, 6 идут впустую, т.к. массив уже упорядочен. В других ситуациях может случиться так, что сортировка закончится только на последнем цикле.
13.4 Сравнительная характеристика методов
Все три метода простой сортировки далеки от идеала, однако в некоторых ситуациях их эффективность может оказаться различной. В связи с этим можно выделить следующие случаи:
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); | ||||||
|
|
K | * | el | nil | ||
| K^.next:=nil; | ||||||
| K^.elem:=el; | ||||||
|
|
L | * | ||||
|
|
K | * | el | nil | ||
|
|
R | * | ||||
| el:=random(10); | ||||||
| while el<>0 | ||||||
|
|
K | * | el | nil | ||
| new(K); | ||||||
| K^.elem:=el; | ||||||
| K^.next:=nil; | ||||||
|
|
L | * | el | * | ||
| R^.next:=K; | ||||||
|
|
R | * | K | el | nil | |
|
|
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);
¦ ¦ K^.elem:= EL; K^.next:= nil;
¦ ¦ R^.next:= K; R:= K;
¦ ¦ EL:= random(10);
¦ end;
end.
ЗАМЕЧАНИЕ. Из программы видно, что L всегда хранит начало очереди, а R - ее конец. Процедура имеет два возвращаемых параметра, которые идентифицируют получаемую с ее помощью очередь. Первый параметр L позволяет начать просмотр очереди или удалить из нее элемент, а второй R - добавить новый элемент (согласно правилу работы с очередями).
Заметим также, что эта процедура формирует очередь из однозначных чисел и признаком конца очереди является число 0. Она предполагает формирование пустой очереди, состоящей из одного нулевого звена:
|
|
* | 0 | nil |
Если пустой очередью считать очередь без единого звена, то процедура принимает вид:
procedure FORMIR_OTCHERED_2 (var L, R: SS);
var K: SS;
EL1, EL2: integer;
begin
¦ {Формирование первого звена очереди }
¦ randomize; EL1:= random(10);
¦ if EL1= 0 then begin L:= nil; R:= L end
¦ else begin new(K);
¦ L:= K; R:= K; K^.next:= nil;
¦ K^.elem:= EL1;
¦ { Помещение очередного элемента в очередь }
¦ EL2:=random(10);
¦ while EL2<>0 do
¦ begin
¦ new(K);
¦ K^.elem:= EL2; K^.next:= nil;
¦ R^.next:= K; R:= K; EL2:= random(10);
¦ end; end;
end.
Одним из приемов работы с очередями является доступ к ее элементу, в частности, сравнение элемента с каким-то числом или вывод его на печать. Исходя из идеологии построения очереди видно, что выборка любого элемента, как и в файле последовательного доступа, возможна только путем просмотра всех элементов очереди, начиная с ее начала. Это легко сделать, зная ссылки на начало и конец очереди. Наличие двух ссылок очень удобно для просмотра очереди (поиска нужного элемента или вывода его на печать). Действительно, в этом случае достаточно организовать цикл с изменением некоторой ссылочной переменной от значения L до значения R.
Таким образом, если необходимо обработать очередь, то следует указать для нее две переменные, где хранятся ссылки на начало и конец. Эти переменные берутся либо непосредственно из программы формирования очереди, либо как выходные параметры процедуры формирования, рассмотренной выше. Ниже следует процедура распечатки элементов очереди, сформированной процедурой пункта 14.1.1:
procedure VIVOD_OTCHERED (var L, R: SS);
var K: SS;
begin
¦ if (L^.elem= 0) or (L= nil) then
¦ writeln('Очеpедь пуста ! ')
¦ else begin
¦ ¦ K:= L;
¦ ¦ write('Элементы очереди: ');
¦ ¦ while K <> R^.next do
¦ ¦ begin
¦ ¦ ¦ write (K^.elem, ' ');
¦ ¦ ¦ K:= K^.next;
¦ ¦ end;
¦ end;
end.
ЗАМЕЧАНИЕ. В данной процедуре знание ссылки R на конец очереди совсем не обязательно. Здесь можно обойтись только ссылкой на начало, а в цикле WHILE в качестве условия взять сравнение значения переменной K с NIL: WHILE K <> NIL.
Добавление нового звена EL к очереди происходит справа (используется указатель R). Рассмотрим сначала алгоритм:
| ОПЕРАТОРЫ | ПОЯСНЕНИЕ | |||||
| read(el); new(K); | ||||||
|
|
K | * | el | nil | ||
| K^.elem:=el; | ||||||
|
|
L | * | el1 | * | ||
|
|
… | … | … | … | … | |
|
|
R | * | elN | * | ||
|
|
||||||
|
|
el | nil | ||||
| K | ||||||
|
|
L | X | el1 | * | ||
|
|
… | … | … | … | … | |
|
|
elN | * | ||||
|
|
R | X | el | nil | ||
| K | ||||||
Запишем теперь процедуру добавления звена к очереди:
procedure DOBAV_OTCHERED (EL:integer; var L, R: SS);
var K: SS;
begin
¦ if L^.elem = 0 then R^.elem:= EL
¦ else if L = nil then
¦ begin
¦ ¦ new(K);L:= K;
¦ ¦ R:= K;
¦ ¦ K^.next:= nil;
¦ ¦ K^.elem:= EL
¦ end
¦ else begin
¦ ¦ new(K);
¦ ¦ K^.elem:=el;
¦ ¦ K^.next:=nil;
¦ ¦ R^.next:=K;
¦ ¦ R:=K
¦ end;
end.
ЗАМЕЧАНИЕ. В данной процедуре сначала проверяется, является ли очередь пустой. Если пустая очередь имеет нулевое звено,то оно заполняется элементом EL. Если же она не содержит звеньев, то создается одно звено по тем же правилам, как при формировании очереди. В общем случае к последнему звену очереди добавляется новое звено.
Исключение звена из очереди происходит слева – используется указатель L - и осуществляется одним оператором: L:=L^.next. При такой операции, однако, память не освобождается. Для ее освобождения необходимо дополнительно использовать процедуру DISPOSE.
|
|
* | el1 | * | |||||
|
|
el2 | * | ||||||
|
|
… | |||||||
|
|
* | elN | nil | |||||
procedure UDALENIE_OTCHERED (var l, r:ss);
begin
¦ if l=nil then writeln('Очеpедь пуста !')
¦ else l:=l^.next
end.
ОБЩЕЕ ЗАМЕЧАНИЕ. В рассмотренных процедурах признаком конца очереди являлось число 0. Если очередь заполняется символами, то для этого нужно выбрать свой признак конца, например, ".". Для ввода символов, как и для ввода чисел, также можно использовать датчик случайных чисел. Но в этом случае он должен генерировать коды ASCII, которые затем с помощью функции преобразования типов CHR трансформировать в сами символы.
Можно элементы очереди вводить с клавиатуры с помощью операторов READLN и READ. При использовании READLN необходимо производить нажатие клавиши ENTER после набора каждого элемента (числа или символа). Оператор же READ позволяет ввести сразу все элементы, заканчивая их набор числом 0 или точкой как признаком конца, причем числа при этом надо отделять друг от друга пробелом. В этом случае для очистки буфера клавиатуры рекомендуется в конце ввода предусмотреть пустой оператор READLN.
Заметим, кстати, что все сказанное о формировании очереди распространяется и на другие типы линейных списков.
14.2 Стек
Стек - это структура данных, которая обеспечивает доступ к списку по принципу LIFO (от первых букв английской фразы "Last Input First Output"): последним вошел, первым вышел. Компонента извлекается из стека таким образом, что первой выбирается та, которая была помещена последней.
В стеке доступна только одна позиция - его вершина, где находится последний по времени занесения элемент. Стек, как и очередь, можно представить в виде динамической цепочки звеньев, где первое звено является вершиной стека. Таким образом, в цепочке, отображающей стек, заглавное звено становится излишним.
Значением указателя, представляющего стек как единый объект, является ссылка на ВЕРШИНУ стека. Последнее звено цепочки – стека содержит в поле ссылок значение NIL.
|
|
* | elN | * | … | el2 | * | el2 | nil | ||
Если стек пуст, то значением указателя является ссылка NIL.
Перед началом заполнения стека его необходимо сделать пустым, т.е. выполнить "обнуление" указателя стека: STACK:= NIL.
Над стеком, как и над очередью, допустимы следующие операции:
1) формирование;
2) занесение нового элемента;
3) удаление элемента;
4) доступ (только для просмотра) к N-му звену стека.
Заметим, кстати, что занесение и удаление происходят в стеке исключительно в его вершине.