Размещено на http://www.allbest.ru/

20

92

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Государственное образовательное учреждение

высшего профессионального образования

«Магнитогорский государственный технический университет им. Г.И. Носова»

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ

ДАННЫХ НА ЭВМ

Утверждено Редакционно-издательским советом университета в качестве учебного пособия

В.Е. Торчинский С.И. Файнштейн

Магнитогорск

2005

УДК 681.3

Рецензенты:

Начальник отдела АСУ и связи ЗАО «МРК»

И. А. Моисеев

Заведующий кафедрой вычислительной техники и систем управления ЦПК «Персонал»

А.Н. Бурыкин

Торчинский В.Е. Файнштейн С.И.

Структуры и алгоритмы обработки данных на ЭВМ: Учебное пособие. Магнитогорск: МГТУ, 2005. 131 с.

ISBN 5-89514-549-3

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

Пособие может быть рекомендовано для студентов специальности «Программное обеспечение вычислительной техники и автоматизированных систем управления» при изучении дисциплины «Структуры и алгоритмы обработки данных на ЭВМ».

УДК 681.3

ISBN 5-89514-549-3©МГТУ им. Г.И. Носова, 2005

©Торчинский В.Е., Файнштейн С.И., 2005

1. ПРОСТЫЕ ТИПЫ ДАННЫХ

Простой тип данных не обладает внутренней структурой и служит для отображения простых фактов и задания базовых компонент структурированных типов.

Классификация простых типов

Кроме интервального и перечисляемого типов, все остальные типы относятся к встроенным.

1.1 Целый тип

Целочисленный тип включает некоторое подмножество целых. Целые типы делят на знаковые и беззнаковые. Если для представления целых чисел в машине используется n разрядов (битов), то диапазон знакового типа составляет от -2^n-1 до 2^n-1-1, а беззнакового - от 0 до 2ⁿ-1.

Считается, что все операции над данными этого типа выполняются точно и соответствуют обычным правилам арифметики. Если результат операции выходит за пределы представимого множества, то ответ будет ошибочным. Например, если X - однобайтовое беззнаковое целое, то результат присваивания X:=250+8 будет равен двум. Такое событие называется переполнением. Компилятор паскаля (в отличие от многих других языков программирования) при включенных соответствующих опциях позволяет отлавливать эту ситуацию и генерировать ошибку времени выполнения.

Следующие арифметические операции считаются стандартными: сложение (+), вычитание (-), умножение (*), целочисленное деление (div) и остаток от деления (mod).

1.2 Вещественный тип

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

1.3 Логический тип

Два значения логического типа обозначаются идентификаторами True и False. Логические операции - это логическая конъюнкция, дизъюнкция и отрицание. Логическая конъюнкция обозначается через AND, логическая дизъюнкция - OR, а отрицание - через NOT. Операции сравнения дают результат логического типа. Таким образом, результат некоторого сравнения можно присвоить какой-то переменной или же использовать в качестве логического операнда в логическом выражении.

1.4 Символьный тип

Символьный тип включает множество символов PC. Наиболее широко распространено множество символов, принятое в качестве стандартного Международной организацией по стандартизации (ISO), и в частности, его американская версия ASCII (American Standard Code for Information Interchange). Это множество состоит из 95 печатаемых (графических) символов и 33 управляющих, последние используются главным образом при передаче данных и для управления печатающими устройствами. Функции ORD() и CHR() позволяют отображать множество символов на множество целых чисел и наоборот.

1.5 Перечисляемый тип

Любой новый простейший тип определяется простым перечислением входящих в него различных значений. Такой тип называется перечисляемым. Его определение имеет следующий вид:

TYPE T = (c₁,c₂,…,c_n),

где T - идентификатор нового типа, а c₁,c₂,…,c_n - идентификаторы новых констант.

Мощность множества T - card(T) = n.

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

1.6 Интервальный тип

Часто приходится сталкиваться с положением, когда переменной присваивается значение некоторого типа, лежащее только внутри определенного интервала значений. Такое положение можно подчеркнуть, определив, что указанная переменная относится к интервальному типу (диапазону). Такой тип задается следующим образом:

TYPE T = <min>..<max>,

где <min> и <max> - выражения, определяющие концы такого диапазона.

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

2. СТРУКТУРИРОВАННЫЕ ТИПЫ ДАННЫХ

Структурированные типы данных предназначены для конструирования сложных структур данных из конечного набора базисных типов.

2.1 Массивы

Массив (функция с конечной областью определения) представляет собой отображение некоторого конечного множества данных на множество данных другого типа. Конечное множество, являющееся областью определения данной функции, называется индексным массивом, а его элементы - индексами. Значение данной функции для некоторого индекса i называется элементом массива, соответствующим i. Множество индексов массива должно быть конечно и обладать возможностью его перечисления, т.е. тип индекса должен быть скалярным. Определение типа массива:

TYPE A = ARRAY[I] OF T₀,

где I - тип индекса; T₀ - тип компонент (базовый тип).

Составное значение массива может задаваться с помощью конструктора массива

CONST A: ARRAY[1..3] OF CHAR = (`a','b','c').

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

Мощность типа массива есть произведение мощностей его компонент. Так как все компоненты типа T относятся к одному базовому типу T₀, то при типе индекса T_I получаем:

card(T) = card(T₀)^card(T_I⁾.

2.2 Алгоритмы поиска в массиве

Задача: найти наименьший индекс i компоненты со значением x в массиве A.

1. Линейный поиск - последовательный просмотр массива с увеличением шаг за шагом той его части, где желаемого элемента не обнаружено:

Var A: Array[1..N] Of T;

…

i := 0;

Repeat

i := i +1

Until (A[i] = x) Or (i = N);

If (a[i] <> x) Then WriteLn('В массиве A нет элемента со значением',x);

2. Метод фиктивного элемента (метод барьера) - метод, позволяющий сократить количество сравнений за счет расположения в конце массива искомого элемента:

Var A:Array[1..N + 1] Of T;

…

i = 0; A[N + 1] = x;

Repeat

i := i + 1

Until (a[i] = x);

If (i>N) Then WriteLn('В массиве A нет элемента со значением',x);

3. Бинарный поиск - метод, основанный на факте, что поиск можно значительно ускорить, если компоненты массива уже отсортированы. Этот метод также называют методом повторного деления пополам интервала, в котором находится нужный элемент. При этом максимальное число требуемых сравнений log₂ N.

i := 1; j := N;

Repeat

k := (i + j) Div 2;

If (i > a[k]) Then i := k + 1

Else j := k - 1;

Until (a[k] = x) Or (i > j);

2.3 Записи (структуры)

Массив объединяет данные с одинаковыми свойствами. В противоположность массиву, записи (структуры) - это объединение компонент, принадлежащих к произвольным, возможно составным типам, в один составной тип. В математике такой составной тип называют прямым, или декартовым произведением типов компонент. Это связано с тем, что множество значений такого составного типа состоит из всех возможных комбинаций значений, взятых по одному из каждого типа компонент. Число таких наборов из n элементов равно произведению количеств элементов всех составляющих множеств, так что кардинальное число такого типа равно произведению кардинальных чисел компонент.

TYPE T = RECORD

S₁:T₁;

…

S_n:T_n;

END;

card(T) = card(T₁)*…*card(T_n).

Значение типа T можно строить с помощью конструктора и присваивать его переменной: x = T(Val₁,…, Val_n).

Поскольку компоненты записи называются полями, то эти имена называются идентификаторами полей. При работе с записями они используются в селекторах, применяемых к переменным-записям. Если существует переменная x:T, то доступ к ее i-му полю может быть осуществлен через x.S_i.

В практической работе кажется удобным и естественным рассматривать два типа как варианты некоторого одного. Например, такой тип как КООРДИНАТЫ можно считать объединением двух его вариантов - прямоугольных и полярных координат, а их составляющими соответственно (а) две длины и (б) длину и угол. Для того чтобы указать, к какому варианту относится та или иная переменная, вводится третья компонента - дискриминант типа или поле признака:

Type Coordinate=Record Case Kind:(Cartesian,Polar) Of { - Kind - поле признака}

Cartesian:(x,y:Real);

Polar:(r,Phi:Real)

End;

Множество значений, определяемое типом Coordinate, есть объединение двух указанных типов: T₁ = (x,y:Real) и T₂ = (r,Phi:Real), и его мощность равна сумме мощностей типов T₁ и T₂ .

Чаще приходится объединять не два полностью различных типа, а два типа с частично совпадающими компонентами. Для такой ситуации применяется термин «запись с вариантами». При использовании записи с вариантами требуется особое внимание. Лучше всего действия, связанные с каждым из вариантов, группировать в выбирающем селекторе, так называемом операторе варианта:

Case Coordinate.Kind Of:

Cartesian:<действия>;

Polar:<действия>;

End;

2.4 Битовые множества

Битовые (паскалевские) множества представляют собой тип данных, значениями которого являются множества всех подмножеств базисного типа:

TYPE T = SET OF T₀;

Значения, имеющие вид множеств, можно присваивать следующим образом:

s:Set Of Char;

…

s := {'e', 'f'};

Мощность множественного типа T равна card(T) = 2^card(T₀⁾.

Это следует из того, что каждый элемент множества представляется в нем в виде одного из двух значений: присутствует или отсутствует, причем все элементы взаимно независимы.

Для всех множественных типов определены следующие элементарные операции:

*- пересечение множеств;

+- объединение множеств;

-- вычитание множеств;

in- проверка на вхождение элемента в множество.

3. ПОСЛЕДОВАТЕЛЬНОСТИ

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

TYPE T = SEQUENCE OF T₀;

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

3.1 Операции над последовательностями

1. Образование последовательности

Последовательность T, состоящую из элементов e₁,…,e_n, представляют в виде T(e₁,…,e_n). В частности, при n=0 последовательность T() называют пустой.

2. Выборка элементов последовательности

Если x - последовательность, то ее элементы можно записать следующим образом:

А) x[i] - i-й элемент;

Б) first(x) - первый элемент;

В) last(x) - последний элемент.

3. Включение и исключение элементов последовательности

А) tail(x) - образование последовательности, исключая из x первый элемент;

Б) initail(x); - образование последовательности, исключая из x последний элемент;

В) appendl(x,e) - образование последовательности с добавлением элемента e слева;

Г) appendr(x,e) - образование последовательности с добавлением элемента e справа.

Например, если последовательность x состоит из элементов e₁,…,e_n, то:

tail(x) = T(e₂,…,e_n)

initail(x) = T(e₁,…,e_n-1)

appendl(x,e) = T(e,e₁,…,e_n)

appendr(x,e) = T(e₁,…,e_n,e)

first(appendl(x,e)) = e

tail(appendl(x,e)) = x

appendl(tail(x),first(x)) = x; при x<>T()

last(appendr(x,e)) = e

initail(appendr(x,e)) = x

appendr(initail(x),last(x)) = x; при x<>T()

3.2 Последовательный файл

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

1) образование пустой последовательности;

2) first(x) - получение первого элемента последовательности;

3) tail(x) - образование последовательности, исключая из x первый элемент;

4) appendr(x,e) - образование последовательности с добавлением элемента e справа.

Другими словами, последовательный файл представляет собой последовательность элементов, которая допускает выборку начального элемента последовательности и добавление элементов в ее конец. Такие последовательности реализуются на внешней запоминающей среде, например, ленте. Причем запись возможна только в одном направлении. Обработка файла реализуется путем введения файловой переменной f, а также дополнительной переменной типа T₀ (T₀ - тип компонентов файла), которая называется буферной переменной. Совокупность значений компонентов файла и положение буферной переменной определяют текущее состояние файла:

f	e1	e2	…	ei	…	en-1	en
	fl	fr

f_l и f_r служат для указания уже просмотренной и еще не просмотренной части файла. С их помощью текущее состояние файла можно задать в виде (f_l, f_r).

3.3 Файл с прямым доступом

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

Пример:

T1 = TEXT; { - последовательный доступ }

T2 = FILE OF <TYPE>; { - прямой доступ }

3.4 Стек

Стек - это последовательность, для которой определены следующие операции:

1) образование пустой последовательности;

2) first(x) - top; - получение первого элемента последовательности;

3) tail(x) - pop; - образование последовательности, исключая из x первый элемент;

4) appendl(x,e) - push; - образование последовательности с добавлением элемента e слева;

5) empty(x) - проверка на пустую последовательность.

Стек (рис. 3.1) - широко используемый тип данных, применяемый, например, для анализа языковых конструкций. Для стека добавление и извлечение элементов возможно только с одного конца последовательности, называющегося вершиной стека (слева). Таким образом, последний добавленный элемент извлекается из стека первым. Поэтому говорят, что стек - это структура с дисциплиной обслуживания «последним пришел - первым ушел» (LiFo).



Рис. 3.1. Стек

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

Примеры

1. Рассмотрим математическое выражение с несколькими уровнями вложенных скобок. Необходимо удостовериться, что скобки расставлены правильно (следует проверить {[( = )]} ). Поэтому все открывающие скобки помещаем в стек, а когда встретится закрывающая, на верхушке стека должна открываться ей парная. После окончания проверки стек должен оказаться пустым.

2. Вычисление алгебраических выражений в постфиксной записи

После чтения очередного операнда он записывается в стек. Когда читается операция, то из стека извлекаются два последних операнда и к ним применяется операция. Результат помещается опять в стек.

ПОКА входная строка не пуста

Symb := следующий символ;

ЕСЛИ Symb = операнд

ТО appendl(x, Symb)

ИНАЧЕ SecondOper := tail(x);

FirstOper := tail(x);

Value := FirstOper (Symb) SecondOper;

appendl(x, Value);

3. Преобразование инфиксной записи в постфиксную с помощью алгоритма Дейкстры

Каждой операции ставится в соответствие некоторый приоритет, а именно: сложение, вычитание - 2, умножение, деление - 3, возведение в степень - 4. Для преобразования используется стек операций.

а. Проверяется очередной символ.

б. Если это операнд, то он передается в выходную строку.

в. Если это открывающая скобка, то она заносится в стек с приоритетом 0.

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

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

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

3.5 Очередь

Очередь - это последовательность, для которой определены следующие операции:

1) образование пустой последовательности;

2) last(x) - получение последнего элемента последовательности;

3) initail(x) - образование последовательности, исключая из x последний элемент;

4) appendl(x,e) - образование последовательности с добавлением элемента e слева;

5) empty(x) - проверка на пустую последовательность.

Часто очередь (рис. 3.2) называют матрицей ожидания. Добавление в очередь осуществляется с левого конца, выборка - с правого. Очередь - это структура с дисциплиной обслуживания «первым пришел - первым ушел» (FiFo - “First input First output”).

Рис. 3.2. Очередь

Часто очередь реализуют на базе вектора, т.е. одномерного массива. Но в силу его ограниченности рано или поздно может наступить такое состояние, что дальнейшее наращивание невозможно, хотя в массиве еще много свободного места. Поэтому очередь реализуется на базе циклического вектора, который позволяет избежать массовых операций, зависящих от количества элементов в очереди. Использование циклического вектора означает, что при достижении конца массива данные в очередь начинают заноситься в освобожденное в его начале место. Например, если в очереди находятся числа 1, 2, 3, 4, 5, 6, 7, а в массиве зарезервировано место для десяти чисел, то хранение очереди в массиве может быть следующим:

6	7	<пусто>	<пусто>	<пусто>	1	2	3	4	5
	Правый конец очереди				Левый конец очереди

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

Пример. Нахождение одного из кратчайших путей в лабиринте.

2	3	X
<1>	2	X	<8>
2	3	X	7
3	4	5	6

1. Помечается исходная клетка значением 1.

2. Каждая новая помеченная клетка помещается в очередь.

3. Из очереди производится выборка клетки, все ее не помеченные соседки помечаются числом, большим на единицу.

4. Продолжаем шаги 2, 3 пока очередь не будет пуста или не будет достигнута клетка назначения.

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

3.6 Дек

Дек - это последовательность, для которой определены следующие операции:

1) образование пустой последовательности;

2) appendl(x,e) - образование последовательности с добавлением элемента e слева;

3) appendr(x,e) - образование последовательности с добавлением элемента e справа;

4) tail(x) - образование последовательности, исключая из x первый элемент;

5) initail(x) - образование последовательности, исключая из x последний элемент;

6) first(x) - получение первого элемента последовательности;

7) last(x) - получение последнего элемента последовательности;

8) empty(x) - проверка на пустую последовательность.

Дек - это «гибрид» очереди и стека, в нем очередь движется как вправо, так и влево (рис. 3.3). Поэтому дек еще называют двусторонней очередью (Double Ended Queue).

Рис. 3.3. Дек

В программах дек реализуют либо на основе циклического вектора, либо на основе двусвязного линейного списка.

4. АЛГОРИТМЫ СОРТИРОВОК

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

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

Зависимость выбора алгоритмов от структуры данных сильна. Методы сортировки обычно разделяют на две категории: сортировка массивов и сортировка файлов. Эти два класса часто называют внутренней и внешней сортировкой, так как массивы располагаются во «внутренней» (оперативной) памяти ЭВМ (для этой памяти характерен быстрый произвольный доступ), а файлы хранятся в более медленной, но более вместительной «внешней» памяти, т.е. на запоминающем устройстве с механическим передвижением (дисках, лентах).

Основные критерии эффективности алгоритмов сортировки следующие:

· быстродействие;

· экономия памяти;

· сокращение времени, затрачиваемого программистом, на реализацию алгоритма.

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

Для определения эффективности алгоритма будем оценивать числа С - необходимых сравнений ключей и М - присваиваний элементов. Эти числа определяются некоторыми формулами от числа n сортируемых элементов. Хорошие алгоритмы сортировки требуют порядка сравнений.

4.1 Сортировка массивов

Введем некоторую терминологию: нам даны элементы - a₁, a₂, …, a_n. Сортировка означает перестановку этих элементов в таком порядке: a_k1, a_k2, …, a_kn, что при заданной функции упорядочения f справедливо отношение f(a_k1)<=f(a_k2)<=…<=f(a_kn).

Обычно функция упорядочения не вычисляется по какому-нибудь правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называют ключом элемента. Для представления элемента a_i будем использовать запись:

type item = record

key: integer;

{описание других компонент}

end;

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

Сортировка называется устойчивой, если записи с одинаковыми ключами остаются в прежнем порядке.

4.1.1 Сортировка вставками

Этот метод обычно используют игроки в карты. Элементы (карты) условно разделяются на готовую последовательность и входную последовательность . На каждом шаге, начиная с I = 2 и увеличивая i на единицу, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя его на подходящее место.

Начальные ключи	44	55	12	42	94	18	06	67
I=2	44	55	12	42	94	18	06	67
I=3	12	42	55	42	94	18	06	67
I=4	12	42	44	55	94	18	06	67
I=5	12	42	44	55	94	18	06	67
I=6	18	12	42	44	55	94	06	67
I=7	06	18	12	42	44	55	94	67
I=8	06	18	12	42	44	55	67	94

При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы «просеивать» x, сравнивая его с очередным элементом и либо вставляя x, либо пересылая направо и продвигаясь налево. «Просеивание» может закончиться при двух различных условиях:

1. Найденный элемент с ключом меньшим, чем ключ x.

2. Достигнут левый конец готовой последовательности.

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

Procedure Sortinsert;

Var i,j : index;

x : item;

Begin

For i:=2 to n do Begin

x:=a[i]; a[0]:=x; j:=i-1;

While x.key < a[j].key do Begin

a[j+1]:=a[j];

j:=j-1;

End;

a[j+1]:=x;

End;

End;

Анализ сортировки простыми включениями. Число сравнений ключей при i-м просеивании составляет самое большее i-1, самое меньшее 1 и, если предположить, что все перестановки n ключей равновероятны, в среднем равно i/2. Число пересылок (присваиваний) равно (учитывая барьер). Поэтому общее число сравнений и пересылок есть:

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

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

procedure binaryinsertion;

var i,j,l,r,m : index;

x : item;

begin

for i:= 2 to n do begin

x:= a[i];

i := 1;

r := i - 1;

while l <= r do begin

m := (l+r) div 2;

if x.key < a[m].key then r:=m - 1

else l := m+1

end;

for j := i - 1 downto l do a[j+1] :=a [j];

a[l] := x;

end;

end;

Анализ сортировки бинарными включениями. Количество сравнений не зависит от исходного порядка элементов. Но из-за округления при делении интервала поиска пополам действительное число сравнений для i элементов может быть на 1 больше ожидаемого. Природа этого «перекоса» такова, что в результате места включения в нижней части находятся в среднем несколько быстрее, чем в верхней части. Это дает преимущество в тех случаях, когда элементы изначально далеки от правильного порядка. На самом же деле минимальное число сравнений требуется, если элементы вначале расположены в обратном порядке, а максимальное - если они уже упорядочены. Следовательно, это случай неестественного поведения алгоритма сортировки

С = n (Log(n) - Log(e) ± 0,5).

К сожалению, улучшение, которое мы получаем, используя метод бинарного поиска, касается только числа сравнений, а не числа необходимых пересылок. В действительности, поскольку пересылка элементов, т.е. ключей и сопутствующей информации, обычно требует значительно больше времени, чем сравнение двух ключей, то это улучшение ни в коей мере не является решающим: важный показатель М по-прежнему остается . И в самом деле, пересортировка уже рассортированного массива занимает больше времени, чем при сортировке простыми вставками с последовательным поиском! Лучших результатов можно ожидать от метода, при котором пересылки элементов выполняются только для отдельных элементов и на большие расстояния. Эта мысль приводит к сортировке выбором.

4.1.2 Сортировка простым выбором

Этот метод основан на следующем правиле:

1. Выбирается элемент с наименьшим ключом.

2. Он меняется местами с первым элементом а[1].

Эти операции затем повторяются с оставшимися n - 1 элементами, затем c n - 2 элементами, пока не останется только один элемент - наибольший.

	44	55	12	42	94	18	06	67
	06	55	12	42	94	18	44	67
	06	12	55	42	94	18	44	67
	06	12	18	42	94	55	44	67
	06	12	18	42	94	55	44	67
	06	12	18	42	44	55	94	67
	06	12	18	42	44	55	94	67
	06	12	18	42	44	55	67	94

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

procedure sortselection;

var i,j,k : index;

x: item;

begin

for i := 1 to n - 1 do begin

k := i; х := a[i];

for j :=i+1 to n do

If a[j] .key < x .key then begin

k := j; x := a[j]

end;

a[k] := a[i]; a[i] := x;

end

end;

Анализ сортировки простым выбором. Очевидно, что число С сравнений ключей не зависит от начального порядка ключей. В этом смысле можно сказать, что сортировка простым выбором ведет себя менее естественно, чем сортировка простыми включениями. Мы получаем

Минимальное число присваиваний равно в случае изначально упорядоченных ключей и принимает наибольшее значение если вначале ключи расположены в обратном порядке. Среднее у Д. Кнута определено как , где =0,577216… (Эйлерова константа).

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

4.1.3 Сортировка простым обменом

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

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

procedure bubblesort:

var i,j: index;

x : item;

begin

for i:=1 to n do begin

for j:=n downto i do

if a[j - 1].key > a[j].key then begin

x:=a[j - 1];

a[j - 1]:=а[j];

a[j]:=x;

end

end

end; {bubblesort]

Начальные ключи	i=2	i=3	i=4	i=5	i=6	i=7	i=8
44	06	06	06	06	06	06	06
55	44	12	12	12	12	12	12
12	55	44	18	18	18	18	18
42	12	55	44	42	42	42	42
94	42	18	55	44	44	44	44
18	94	42	42	55	55	55	55
06	18	94	67	67	67	67	67
67	67	67	94	94	94	94	94

Этот алгоритм легко оптимизировать. Этот пример показывает, что три последних прохода никак не влияют на порядок элементов, поскольку те уже рассортированы. Очевидный способ улучшить данный алгоритм - это запоминать, производился ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм может закончить работу. Этот процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и место (индекс) последнего обмена. Ведь ясно, что все пары соседних элементов с индексами, меньшими этого индекса k, уже расположены в нужном порядке. Поэтому следующие проходы можно заканчивать на этом индексе, вместо того чтобы двигаться до установленной заранее нижней границы i. Однако, если внимательней присмотреться, можно заметить странную асимметрию: один неправильно расположенный «пузырек» в «тяжелом» конце рассортированного массива всплывет на место за один проход, а неправильно расположенный элемент в «легком» конце будет опускаться на правильное место только на один шаг на каждом проходе.

Например, массив

1218424455679406

будет рассортирован при помощи метода пузырька за один проход, а сортировка массива

9406121842445567

потребует семи проходов. Эта неестественная асимметрия подсказывает третье улучшение: менять направление следующих один за другим проходов. Мы назовем полученный в результате алгоритм шейкер-сортировкой.

I=2	3	3	4	4
R=8	8	7	7	4
44	06	06	06	06
55	44	44	12	12
12	55	12	44	18
42	12	42	18	42
94	42	55	42	44
18	94	18	55	55
06	18	67	67	67
67	67	94	94	94

procedure shakersort;

var j,k,l,r : integer;

x: item;

begin

l := 2; r := n; k:= n;

repeat

for j:=r downto l do

if a[j - 1].key > a[j].key then begin

x := a[j - 1];

a[j-1] := a[j];

a[j] := x;

k := j;

end;

l := k + 1;

for j := l to r do

if a[j - 1].key > a[j].key then begin

x := а[j - 1];

a[j - 1] := a[j];

a[j] := x;

k:=j;

end ;

r := k - 1;

until l > r;

end; {shakersort}

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

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

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

Можно показать, что среднее расстояние, на которое должен переместиться каждый из n элементов во время сортировки, - это n/3 мест. Это число дает ключ к поиску усовершенствованных, т. е. более эффективных методов сортировки. Все простые методы в принципе перемещают каждый элемент на одну позицию на каждом элементарном шаге. Поэтому они требуют порядка n² таких шагов. Любое улучшение должно основываться на принципе пересылки элементов за один цикл на большее расстояние.

4.1.4 Сортировка Шелла

Некоторое усовершенствование сортировки простыми вставками было предложено Д.Л. Шеллом в 1959 г. Этот метод продемонстрируем на примере из восьми элементов (рис. 4.1).

Рис. 4.1. Сортировка Шелла

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

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

Очевидно, что этот метод в результате дает упорядоченный массив, и также совершенно ясно, что каждый проход будет использовать результаты предыдущего прохода, поскольку каждая i-сортировка объединяет две группы, рассортированные предыдущей 2i-сортировкой. Также ясно, что приемлема любая последовательность приращений, лишь бы последнее было равно 1, так как в худшем случае вся работа будет выполняться на последнем проходе. Однако менее очевидно, что метод убывающего приращения дает даже лучшие результаты, когда приращения не являются степенями двойки.

Таким образом, программа разрабатывается вне связи с конкретной последовательностью приращений. Все t приращений обозначаются через с условиями .

Каждая h-сортировка программируется как сортировка простыми включениями, при этом, для того чтобы условие окончания поиска места включения было простым, используется барьер.

Ясно, что каждая h-сортировка требует собственного барьера и что программа должна определять его место как можно проще. Поэтому массив a нужно дополнить не одной компонентой а [0], a компонентами, так что теперь он описывается как

а: array [-.. n] of item;

Вот так будет выглядеть алгоритм сортировки Шелла для t = 4.

procedure shellsort;

const t = 4;

var i,j,k,s: index;

x: item;

m: 1..t;

h: array [1..t] of integer;

begin

h[1] := 9; h[2] := 5; h[3] := 3; h[4] := 1;

for m := 1 to t do begin

k := h[m];

s := - k; {место барьера}

for i := k + 1 to n do begin

x := a[i]; j := i-k;

if s=0 then s := - k;

s := s + 1; a[s] := x;

while x .key < a[j] .key do begin

a[j+k] := a[j]; j := j-k

end ;

a[j+k] := x;

end

end

end;

Анализ сортировки Шелла. При анализе этого алгоритма возникают некоторые очень сложные математические задачи, многие из которых еще не решены. В частности, неизвестно, какая последовательность приращений дает лучшие результаты. Однако выявлен удивительный факт, что они не должны быть кратны друг другу. Это позволяет избежать явления, которое видно в приведенном выше примере, где каждый проход сортировки объединяет две цепочки, которые ранее никак не взаимодействовали. В действительности желательно, чтобы взаимодействие между разными цепочками происходило как можно чаще. Можно сформулировать следующую теорему:

Если k-рассортированная последовательность i-сортируется, то она остается k-рассортированной.

Д. Кнут указывает, что разумным выбором может быть такая последовательность приращений (записанная в обратном порядке):

1, 4, 13, 40, 121, ...,

где и .

Он рекомендует также последовательность

1, 3, 7, 15, 31, ...,

где и .

Дальнейший анализ показывает, что в последнем случае затраты, которые требуются для сортировки n элементов с помощью алгоритма сортировки Шелла, пропорциональны n^6/5. Это значительное улучшение по сравнению с n².

4.1.5. Пирамидальная сортировка

Метод сортировки простым выбором основан на повторном выборе наименьшего ключа среди n элементов, затем среди n-1 элементов и т.д. Понятно, что поиск наименьшего ключа из n элементов требует n-1 сравнений, а поиск его среди n-1 элементов требует n-2 сравнений. Итак, как можно улучшить эту сортировку выбором? Это можно сделать только в том случае, если получать от каждого прохода больше информации, чем просто указание на один, наименьший элемент. Например, с помощью n/2 сравнений можно определить наименьший ключ из каждой пары, при помощи следующих n/4 сравнений можно выбрать наименьший из каждой пары таких наименьших ключей и т. д. Наконец, при помощи всего n-1 сравнений мы можем построить дерево выбора и определить корень как наименьший ключ.

На втором шаге мы спускаемся по пути, указанному наименьшим ключом, и исключаем его, последовательно заменяя на «дыру».

Затем заполняем «дыры».

Элемент, оказавшийся в корне дерева, вновь имеет наименьший ключ (среди оставшихся) и может быть исключен. После n таких шагов дерево становится пустым (т. е. состоит из «дыр») и процесс сортировки закончен. Отметим, что каждый из n шагов требует лишь сравнений. Поэтому вся сортировка требует лишь порядка элементарных операций, не считая n шагов, которые необходимы для построения дерева. Это значительное улучшение по сравнению с простым методом, требующим n² шагов, и даже по сравнению с сортировкой Шелла, которая требует n^1,2 шагов.

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

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

Пирамида (рис. 4.2) определяется как последовательность ключей , такая, что для всякого

i = l, ..., r/2.

.

Рис. 4.2. Пирамида

Теперь предположим, что дана пирамида с элементами h[l+1],…,h[r] для некоторых значений I и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду h[l],...,h[r]. Возьмем, например, исходную пирамиду h[1], ...,h[7], показанную на рис. 4.3, и расширим эту пирамиду «влево», добавив элемент h[i] = 44.

Рис. 4.3. Пирамида до просеивания

Новый элемент x сначала помещается в вершину дерева, а затем «просеивается» по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом формируется новая пирамида. В данном примере значение 44 сначала меняется местами с 06, затем с 12, и так формируется новое дерево (рис. 4.4).

Рис. 4.4. Пирамида после просеивания

Изящный способ построения пирамиды был предложен Р.У. Флойдом. В нем используется следующая процедура просеивания. Дан массив h[1]…h[n]. Ясно, что элементы h[n/2+1]…h[n] уже образуют пирамиду, поскольку не существует двух индексов i, j, таких, что j = 2i (или j = 2i + 1). Эти элементы составляют последовательность, которую можно рассматривать как нижний ряд соответствующего двоичного дерева, где не требуется никакого упорядочения.

procedure sift(l,r: index);

label 13;

var i,j : integer;

x : item;

begin

i := l; j := 2*i; x := a[i];

while j<=r do begin

if (j<r) and (a[j].key > a[j+1].key) then

j:= j+1;

if x.key <= a[j].key then break;

a[i]:=a[j]; i:=j; j:=2*i

end;

a[i] := x;

end;

Теперь пирамида расширяется влево: на каждом шаге добавляется новый элемент и при помощи просеивания помещается на соответствующее место (рис. 4.5).

Рис. 4.5. Образование пирамиды

Для того чтобы рассортировать элементы, надо выполнить n-1 шагов просеивания: после каждого шага из пирамиды выбирается последняя компонента (скажем, x), верхний элемент пирамиды помещается на освободившееся место x, а x просеивается на свое место.

В результате мы получаем последовательность в обратном порядке (рис. 4.6). Но это легко можно исправить, изменив направление отношения порядка в процедуре sift.

Рис. 4.6. Сортировка

procedure heapsort;

var l,r : index;

x : item;

procedure sift;

………………………………………………………

begin

l := (n div 2) + 1; r := n;

while l>1 do begin

l:=l-1; sift;

end ;

while r>1 do begin

x:= a[1]; a[1] := a[r]; a[r] := x;

r:=r -1; Sift;

end

end; {heapsort}

Анализ пирамидальной сортировки. С первого взгляда неочевидно, что этот метод сортировки дает хорошие результаты. Ведь элементы с большими ключами вначале просеиваются влево, прежде чем, наконец, окажутся справа. Действительно, эта процедура не рекомендуется для такого небольшого числа элементов. Однако для больших n пирамидальная сортировка оказывается очень эффективной, и чем больше n, тем она эффективнее - даже по сравнению с сортировкой Шелла.

В худшем случае необходимо n/2 шагов, которые просеивают элементы через log(n/2), log(n/2 - 1), ..., log (n - 1) позиций (здесь берется целая часть логарифма по основанию 2). Следовательно, на фазе сортировки происходит n - 1 просеиваний с самое большее log(n - 1), log(n - 2) ,..., 1 пересылками. Кроме того, требуются n - 1 пересылок для того, чтобы отложить просеянный элемент вправо. Отсюда видно, что пирамидальная сортировка требует шагов даже в худшем случае. Такие отличные характеристики для худшего случая - одно из самых выгодных качеств пирамидальной сортировки.

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

Среднее число присваиваний равно приблизительно и отклонения от этого значения сравнительно малы.

4.1.6 Быстрая сортировка

Эта сортировка основана на принципе обмена. Учитывая, что сортировка методом пузырька в среднем была наименее эффективной из трех алгоритмов простой сортировки, мы должны требовать значительного улучшения. Однако, усовершенствование сортировки, основанной на обмене, дает вообще лучший из известных до сего времени метод сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель К. Хоор (C. Hoare) окрестил его быстрой сортировкой.

Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях. Предположим, что нам даны n элементов с ключами, расположенными в обратном порядке. Их можно рассортировать, выполнив всего n/2 обменов, если сначала поменять местами самый левый и самый правый элементы и так постепенно продвигаться с двух концов к середине. Разумеется, это возможно, только если мы знаем, что элементы расположены строго в обратном порядке. Но все же этот пример наводит на некоторые мысли.

Попробуем рассмотреть следующий алгоритм: выберем случайным образом какой-то элемент (назовем его x), просмотрим массив, двигаясь слева направо, пока не найдем элемент a[i] > x, а затем просмотрим его справа налево, пока не найдем элемент а[j] < x. Теперь поменяем местами эти два элемента и продолжим процесс «просмотра с обменом», пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами, меньшими, чем x, и правую - с ключами, большими x.

Если, например, в качестве x выбрать средний ключ, равный 42, из массива ключей

4455124294061867,

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

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

procedure quicksort;

procedure sort (l,r : index);

var i,j : index;

x,w : item;

begin

i := l; j := r;

x := a[(l+r) div 2];

repeat

while a[i].key < x.key do i := i + 1;

while x.key < a[j].key do j := j - 1;

if i <= j then begin

w := а[i]; а[i] := a[j]; a[j] := w;

i:= i + 1 ;.j:= j - 1;

end

until i > j;

if l < j then sort(l,j);

if i < r then sort(i,r);

end ;

begin

sort(1,n);

end; {quicksort}

Анализ быстрой сортировки. Среднее количество сравнений и присваиваний составляет:

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

Тем не менее, остается проблема наихудшего случая. Как тогда ведет себя быстрая сортировка? Ответ, к сожалению, разочаровывает. Здесь проявляется слабость быстрой сортировки (которая в таких случаях становится «медленной сортировкой»). Рассмотрим, например, когда каждый раз в качестве x выбирается наибольшее значение в подмассиве. Тогда каждый шаг разбивает сегмент из n элементов на левую часть из n - 1 элементов и правую часть, состоящую из одного элемента. В результате вместо log(n) необходимо n разбиений и скорость работы в наихудшем случае оказывается порядка n².