3345

гибкости, но потеряли некоторую информацию. При последовательном представлении фиксированное соотношение между i и ячейкой Si (то есть между индексом и элементом последовательности, соответствующем индексу) позволяет, в частности, иметь быстрый и прямой доступ к любому элементу последовательности. В связанном распределении такого соотношения не существует, а доступ ко всем элементам последовательности, кроме первого, не является прямым и эффективным. Например, при последовательном представлении, если длина последовательности задана, то легко найти средний ее элемент; это же самое сделать труднее, если последовательность задается связанным списком. Кроме того, приходится тратить память на указатели Pi.

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

3.11.3. Стеки и очереди У данных структур изменения происходят только в концах

последовательностей.

Алгоритм оперирования со стеком, чувствительный элемент которого обозначается TOP (вершина), рассмотрим на примере выяснения правильности построения выражения. Такая задача возникает при компиляции программ.

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

Пусть дана последовательность скобок g={[ ] ({[( )]}{ })}.

201

Элементы g будем обозначать x1, x2,…, xn, где xi есть одна из скобок {,},(,),[ или ]. Элементы [,( и [ назовем левыми символами; скажем, что xi – левый партнер xj, если xi=[ и xj=], или xi=( и xj=), или xi={ и xj=}.

Algorithm WELL FORMED (ПРАВИЛЬНО ПОСТРОЕННАЯ). Определяет, является ли произвольная последовательность символов x1, x2,…, xn, где каждый xi – одна из скобок {,},(,),[ или ], правильно построенной.

Шаг 0. [Инициализация] Set TOP 0; J 1.//TOP – вершина стека. Шаг 1. [Читается последовательность скобок слева направо]

While I N do through шаг 3od.

Шаг 2. [Записывается в стек левый символ]

If xi левый символ then [записывается xi] else [выбирается символ из стека]

if TOP левый партнер xi

then выбрать элемент TOP из памяти else напечатать «НЕПРАВИЛЬНО

ПОСТРОЕННАЯ»;

and STOP fi

Шаг 3. [Прочесть следующий символ] Set I I+1.

Шаг 4. [Память пуста?] If TOP=0 then PRINT «ПРАВИЛЬНО ПОСТРОЕННАЯ»; else PRINT «НЕПРАВИЛЬНО ПОСТРОЕННАЯ» fi; and STOP.

202

3.12 Основные алгоритмы определения и использования закономерностей в структурах

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

Сортировка стала важным предметом вычислительной математики, ибо более 25 % машинного времени расходуется на сорти-

203

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

Эффективность алгоритмов сортировки зависит от большого числа факторов: (1) каково число сортируемых элементов; (2) все ли элементы могут быть помещены в оперативную память; (3) до какой степени элементы уже отсортированы; (4) каковы диапазон и распределение (по диапазону) значений сортируемых элементов;

(5) каковы длина, сложность и требования к памяти алгоритма сортировки; (6) возможность включения и исключения элементов; (7) возможность параллельного сравнения элементов.

Обычно сортируемые элементы представляют собой записи данных определенного вида. Каждая запись имеет поле ключа (указателя, имени) и поле информации. При этом записи упорядочиваются по значению ключа (имени). То есть ключ управляет процессом сортировки. Каждое имя xi принимает значение из пространства имен x1, x2, …, xn, на котором определен линейный порядок. Будем считать, что никакие два имени не имеют одинаковых значений; то есть любые xi, xj обладают тем свойством, что если i j, то xi<xj или xi>xj. Наша цель состоит в том, чтобы выяснить упорядочивающую перестановку П=( 1, 2, …, n) для которой

x 1<x 2<…<x n.

Как правило, при этом вырабатывают саму упорядоченную последовательность {xi}, а не упорядочивающую перестановку П. В задаче полной сортировки требуется полностью определить П, в задачах частной сортировки требуется извлечь либо только частичную информацию о П (например, Пi для некоторых значений i), либо полностью определить П по некоторой заданной частичной информации о ней (например, слияние двух упорядоченных таблиц).

Задача полной сортировки бывает внутренней и внешней. Внутренняя сортировка имеет место в случае малой таблицы, умещающейся непосредственно в адресной памяти. Внешняя сор-

204

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

Существует по крайней мере пять классов алгоритмов внутренней сортировки.

1.Вставка. На i–ом этапе имя xi помещается на надлежащее место между i-1 уже отсортированными именами.

2.Обмен. Два имени, расположение которых не соответствует порядку, меняются местами. Процедура повторяется до тех пор, пока не остаются такие пары.

3.Выбор. На i–ом этапе из неотсортированных имен выби-

рается xi наибольшее (наименьшее) имя и помещается на соответствующее место.

4.Распределение. Имена распределяются по группам, и содержимое группы затем объединяется таким образом, чтобы частично отсортировать таблицу; процесс повторяется до полной отсортировки.

5.Слияние. Таблица делится на подтаблицы, которые сортируются по отдельности и затем сливаются в одну.

Эти классы нельзя назвать ни взаимоисключающими, ни исчерпывающими; одни алгоритмы сортировки можно с полным основанием отнести более, чем к одному классу.

При этом предполагается, что имена нужно сортировать на месте, то есть их переразмещение должно происходить внутри последовательности х1, х2, …, хn, для чего имеется одна – две дополнительные ячейки для временного размещения имен. То есть перенос имен в другую область памяти не допускается.

Любой алгоритм сортировки в линейном упорядоченном пространстве имен (если xi xj, то либо xi<xj или xi>xj) можно представить в виде расширенного бинарного дерева решений. В нем каждый узел соответствует сравнению имен, а каждый лист (висячая вершина) – исходу алгоритма.

205

>Сравнение х1 и x3

Бинарное дерево для сортировки трех имен

Корень дерева изображен в виде овала с отношением х1 : х2, что означает, что алгоритм начинает работу сравнением имен х1 и х2. Две исходящие из корня ветви ведут к поддеревьям, определяющим продолжение работы алгоритма после каждого из двух возможных исходов первого сравнения. Это дерево можно рассматривать как блок-схему алгоритма сортировки, в котором все циклы «размотаны» и показаны только сравнения имен. Две дочери узла изображают два возможных исхода сравнения. В таком дереве решений каждая перестановка определяет единственный путь от корня к висячей вершине (листу).

3.12.1. Сортировка вставками Простейший алгоритм сортировки вставками выглядит сле-

дующим образом. Он проходит через этапы j=2, 3, …, n: на этапе j имя xj вставляется на свое правильное место среди x1, x2, …, xj-1. При вставке имя xj временно размещается в «запасной» ячейке Х. Все оставшиеся имена xj-1, xj-2, …, x1 сравниваются с Х и сдвигаются вправо, если обнаруживается, что они больше Х. Фиктивное имя

206

х0 служит для остановки просмотра слева. На рис. алгоритм проиллюстрирован на примере таблицы из 5 имен.

В «полусинтаксическом» виде алгоритм выглядит следующим образом.

Algorithm SIS (Сортировка прямым включением (вставками - Ю.Б.). Отсортировать на старом месте (без заведения новой последовательности) последовательность целых чисел I(1), I(2), …, I(N) в порядке возрастания.

Шаг 1. [Основная итерация]

Шаг 4. [Включение] Set I(L+1) K.

207

Эффективность алгоритмов сортировки определяется средним числом сравнений, необходимых для получения упорядоченного ряда ключей. В среднем, когда все перестановки равновероятны, это число равно N!

3.12.2. Обменная сортировка Обменная сортировка некоторым систематическим образом

меняет местами пары имен, не отвечающие порядку до тех пор, пока такие пары существуют.

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

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

b n [присвоение]

bt

Валгоритме используется переменная b, значение которой в начале цикла while равно наибольшему индексу t, такому, что про

имя xt еще не известно, стоит ли оно на окончательной позиции. Это проверяется сравнением «xj>xj+1» и в случае удовлетворения

производится замена «xj xj+1».

Число обменов в алгоритме пузырьковой сортировки равно числу инверсий. Под инверсией понимается пара (xi,xj), если i<j и xi>xj. Вектор инверсий последовательности чисел X=(x1,x2, …,xn) - это последовательность целых чисел d1,d2, …,dn таких, что dj – число элементов xi, по номеру меньших j, таких, что (xi,xj) является инверсией. Другими словами, dj – число элементов, больших xj и стоящих слева от него в последовательности, так что 0 dj<j. При-

208

мер пузырьковой сортировки с вычислением вектора инверсий показан на рисунке.

Особый интерес к векторам инверсий основан на том факте, что вектор инверсий (и особенно сумма его компонент) несет информацию о количестве «беспорядка» в перестановке. Эта величина полезна при анализе алгоритмов сортировки.

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

том, чтобы идти по шагам i=1, 2, …, n, находя i-ое наибольшее (наименьшее) имя в паре имен xi : xi+1, оставляя его (турнир с выбыванием). Ее суть хорошо видна из следующего рисунка.

209