Уточненный рекурсивный алгоритм быстрой сортировки.

Исходные данные: Массив А; Левая_граница (0); Правая_граница (n -1)

1. Индекс в начале, i = Левая_граница.

2. Индекс в конце, j =Правая_граница.

3. Опорный = A [(Левая_граница + Правая_граница) / 2].

4. Повторять

4.1. Движение слева направо:

Пока A[i ] < Опорный

i = i + 1

4.2. Движение справа налево:

Пока A[j ] > Опорный

j = j - 1.

4.3. Поменять местами A[i ] и A[j ].

4.4. i = i + 1.

4.5. j = j - 1.

Пока Левая_граница < Правая_граница.

5. Если Левая_граница < j, то отсортировать А от Левая_граница до j,

6. Если i > Правая_граница, то отсортировать А от i до Правая_граница.

7. Вывести массив А.

 

Алгоритм 8. Сортировка Шелла

 

Метод является ускоренным вариантом сортировки вставками. При этом ускорение достигается за счет увеличения расстояния, на которое перемещаются элементы. Исходный массив делится на d частей, содержащих n / d элементов каждый (последний подмассив может быть короче). Подмассивы содержат элементы с номерами [0, d, 2 d и т.д.], [1, d + 1, 2 d +1 и т.д.], [2, d + 2, 2 d +2 и т.д.] и т.д.

Вначале сравниваются и упорядочиваются с помощью алгоритма вставок элементы, отстоящие один от другого на расстоянии d, т.е. имеющие номера 0 и 1, d и d + 1, 2 d и 2 d + 1 и т.д. Затем процедура повторяется при меньших значениях d, например, d / 2. Завершается алгоритм упорядочением элементов при d = 1, то есть обычной сортировкой вставками. Мы рассмотрим сортировку Шелла для начального значения d, равного n /2, и будем последовательно уменьшать его вдвое.

Алгоритм сортировки Шелла

1. Задать массив А из n чисел.

2. Выполнять

2.1. d = n / 2.

2.2. Для i от 0 до n – d с шагом d

2.2.1. j = i.

2.2.2. x = A_i

2.2.3. Пока (j ≥ d) (A[j] > A[j + d])

a) A[j] = A[j + d]

b) j = j – d.

2.3. d = d / 2.

Пока d > 0.

3. Вывести массив А.

1. Закончить.

 

Порядок выполнения лабораторной работы

 

Работа предполагает выполнение следующих этапов.

1. Знакомство со всеми разделами руководства.

2. Получение у преподавателя задания на разработку программы для алгоритмов сортировки (см. Приложение 4).

3. Разработка и отладка заданных программ.

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

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

 

Содержание отчета о выполненной работе

 

Отчет о выполненной работе должен содержать.

1. Название и цель работы.

2. Словесное описание заданных алгоритмов сортировки.

3. Тексты программ.

4. Формулы верхней оценки временной и емкостной сложности заданных алгоритмов.

5. Результаты экспериментальной оценки временной и емкостной сложности заданных алгоритмов.

Контрольные вопросы

 

1. Что такое сортировка и для чего она нужна?

2. По каким признакам выполняется классификация алгоритмов сортировки?

3. Как оценивается временная сложность алгоритмов упорядочения?

4. Как оценивается емкостная сложность алгоритмов сортировки?

5. Какой метод упорядочения самый простой?

6. Какой алгоритм сортировки самый быстрый?

7. Какие алгоритмы пригодны для упорядочения файлов?

8. Чем отличается сортировка чисел от строк?

9. Как Вы определили время выполнения Ваших алгоритмов?

10. Как Вы определили объем памяти, необходимой для выполнения Ваших алгоритмов?

11. Каковы основные отличия сортировки вставками от «пузырьковой»?

12. Каковы основные отличия упорядочения слиянием от «пузырьковой»?

13. Каковы основные отличия сортировки слиянием от метода Боуза-Нельсона?

14. Каковы основные отличия упорядочения слиянием и вставками?

15. Каковы отличительные особенности быстрой сортировки?

16. Как выполняется упорядочение Шейкером?

17. Каковы особенности сортировки Шелла и для каких данных она предпочтительна?

18. У каких известных Вам методов сортировки временная сложность зависит от объема используемой памяти?

 

Лабораторная работа №5
ИССЛЕДОВАНИЕ И ОЦЕНКА
АЛГОРИТМОВ ПОИСКА НА ДЕРЕВЬЯХ

Краткая теория

 

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

 

Двоичные и В+ деревья.
Основные понятия и определения

 

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

Древовидная структура содержит множество узлов (nodes), происходящих от единственного начального, который называют корнем (root). На Рис. 5.1 корнем является узел А. Принято узел считать родителем (parent), указывающим на 0, 1 или более других узлов, называемых сыновьями (children). Например, узел В является родителем сыновей E и F. Дерево может представлять несколько поколений. Сыновья узла и сыновья их сыновей называются потомками (descendants), а родители и прародители – предками (ancestors) этого узла. Например, узлы E, F, I, J – потомки узла B. Каждый некорневой узел имеет только одного родителя, и каждый родитель имеет 0 или более сыновей. Узел, не имеющий детей (E, G, H, I, J), называется листом (leaf).

Каждый узел дерева является корнем поддерева (subtree), которое включает в себя этот узел и всех его потомков. Так, F есть корень поддерева, содержащего узлы F, I и J. Узел G является корнем поддерева без потомков. Таким образом, узел A есть корень поддерева, которое само оказывается деревом.

Рис. 5.1. Графическое изображение дерева

 

Каждый узел дерева является корнем поддерева (subtree), которое включает в себя этот узел и всех его потомков. Так, F есть корень поддерева, содержащего узлы F, I и J. Узел G является корнем поддерева без потомков. Таким образом, узел A есть корень поддерева, которое само оказывается деревом.

Переход от родительского узла к дочернему и другим потомкам осуществляется вдоль пути (path). Например, на рисунке 5.2 путь от корня A к узлу F проходит от A к B и от B к F. Тот факт, что каждый некорневой узел имеет единственного родителя, гарантирует, что существует единственный путь из любого узла к его потомкам. Длина пути от корня к этому узлу есть уровень узла. Уровень корня равен 0. Каждый сын корня является узлом 1-го уровня, следующее поколение – узлами 2-го уровня и т.д. Например, на рисунке 5.2 узел F является узлом 2-го уровня с длиной пути 2.

Рис. 5.2. Уровень узла и длина пути

 

Глубина (depth) дерева есть его максимальный уровень. Понятие глубины также может быть описано в терминах пути. Глубина дерева есть длина самого длинного пути от корня до узла. На рис. 5.2 глубина дерева равна 3.

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

 

Рис. 5.3. Бинарные деревья

 

У каждого узла бинарного дерева может быть 0, 1 или 2 сына. Причем, узел слева называют левым сыном (left child), а справа – правым (right child). Эти наименования связаны с графическим представлением дерева. Двоичное дерево является рекурсивной структурой. Каждый узел – это корень своего собственного поддерева. У него есть сыновья, которые сами являются корнями деревьев, которые называются левым и правым поддеревьями соответственно.

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

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

Двоичное дерево - это такое множество узлов B, что

a) B является деревом, если множество узлов пусто (пустое дерево – тоже дерево);

b) B разбивается на три непересекающихся подмножества:

· { R } корневой узел;

· { L₁, L₂,..., L_m } левое поддерево R;

· { R₁, R₂,..., R_m } правое поддерево R.

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

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

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

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

Почти полное бинарное дерево представляет собой бинарное дерево, для которого существует неотрицательное целое k такое, что:

1) каждый лист в дереве имеет уровень k или k+1;

2) если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.

В программировании структура бинарного дерева образуется элементами, структура которых приведена на рисунке 5.4. Узел содержит поле данных и два поля с указателями: левым (left) и правым (right), поскольку они указывают на соответствующие поддеревья. Значение NULL является признаком пустого дерева.

Корневой узел определяет входную точку дерева, а поля указателей – узлы следующего уровня. Листовой узел содержит NULL в полях правого и левого указателей. В java узел представляется объектом класса с соответствующей структурой,
например.

 

 

Рис. 5.4. Представление узлов дерева в программировании

 

 

class Tree{

public Tree left; // левый указатель

public Tree right; // правый указатель

public int key; // информационное поле целого типа

}

Другой пример – дерево, узел которого хранит его обозначение в виде латинской буквы с номером и числовое поле. Корень обозначается буквой А, узлы 2-го уровня – В, 3-го – С и т.д. Нумерация узлов k -ого уровня выполняется от 1 до 2^k.

Class MyTree{

// Уровень узла

private char Level;

// Номер узла

private int Number;

// Поле узла

private int key; }

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

A

B

E

F

I

J

C

G

D

H

В и В+ деревья

 

B-дерево является разновидностью дерева поиска. Такая структура была предложена Р. Бэйером и Е. МакКрейтом в 1970 году. Характерной для В-дерева является его малая глубина (высота), обычно равная 2 - 3. Основными свойствами таких деревьев являются: сбалансированность, ветвистость, отсортированность и логарифмическое время выполнения всех стандартных операций (поиск, вставка, удаление). Сбалансированность означает, что все листья находятся на одинаковом расстоянии от корня. В отличие от бинарных, В-деревья допускают большое число потомков для любого узла. Это свойство называется ветвистостью. Благодаря ему, В-деревья очень удобны для хранения крупных последовательных блоков данных, поэтому такая структура часто находит применение в базах данных и файловых системах.

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

1. Каждый узел содержит строго меньше m (порядок дерева) потомков.

2. Каждый узел содержит не менее m /2 потомков.

3. Корень может содержать меньше m /2 потомков.

4. У корневого узла есть хотя бы 2 потомка, если он не является листом.

5.
Все листья находятся на одном уровне и содержат только данные (ключи).

Пример В-дерева приведен на рисунке 5.5.

Рис. 5.5. Пример В+ дерева.
Стрелки идут к потомкам. В ключах записаны числа

 

Действия с бинарными и В+ деревьями

 

Узлы дерева обычно используются для хранения информации. Основными операциями над деревьями являются:

1) построение дерева,

2) создание узла,

3) включение узла в дерево,

4) удаление узла из дерева,

5) обход дерева,

6) поиск элементов (узлов).

 

Построение бинарного дерева

 

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

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

Рассмотрим пример формирования двоичного дерева. Предположим, что нужно сформировать двоичное дерево, узлы (элементы) которого имеют следующие значения признака: 20, 10, 35, 15, 17, 27, 24, 8, 30. В этом же порядке они и будут поступать для включения в двоичное дерево.

Первым узлом в дереве (корнем) станет узел со значением 20. В общем случае, поиск места подключения очередного элемента всегда начинается с корня. К корню слева подключается элемент 10, а справа - 35. Далее элемент 15 подключается справа к 10, проходя путь: корень 20 - налево - элемент 10 - направо - подключение, так как дальше пути нет. Процесс продолжается до тех пор, пока не будут включены в дерево все элементы. Результат представлен на рис. 5.6.

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

Узлы, у которых заполнены два адреса связи считаются полными, а с одним адресом – неполными. Элементы с двумя незаполненными адресами называются концевыми (листьями).

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

 

 

Рис. 5.6. Построение бинарного дерева.

Значения элементов дерева: 20, 10, 35, 15, 17, 27, 24, 8, 30

 

Алгоритм построения упорядоченного бинарного дерева может быть сформулирован так.

1.Первый элемент с ключом р [1] становится корнем дерева.

2.Значение ключа второго узла р [2] сравнивается с р [1] (корня дерева). Если р [2] < p [1], то второй элемент помещается на левой от корня ветви, в противном случае – на правой. В результате будет получено упорядоченное дерево из первых двух узлов.

3. Далее на каждом шаге создается упорядоченное дерево из первых i элементов. Выбор i -го узла производится следующим образом. Ключ р [ i ] сравнивается с корневым значением и выполняется переход по левому адресу (если р [1]> р [ i ]), в противном случае (при р [1] <= р [ i ]) – по правому адресу. Далее ключ достигнутого узла также сравнивается с р [ i ], и снова организуется переход по левому и правому адресу и т.д. При нахождении незаполненного адреса связи ему присваивается ключ р [ i ].

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

Из рассмотренного алгоритма следует, что основным методом, используемым при построении двоичного дерева и решении других задач, является поиск. В процессе поиска в упорядоченном бинарном дереве просматривается некоторый путь, начинающийся всегда в его корне. Искомое значение ключа q сравнивается со значением корня р [1]. Если р [1]> q, просмотр дерева продолжается по левой от корня ветви, иначе (если р [1] <= q) – по правой. Для произвольного узла с ключом р [ i ] могут быть получены следующие результаты сравнения:

a) р [ i ] = q – элемент, удовлетворяющий условию поиска найден, и поиск заканчивается по правой ветви.

b) р [ i ] > q – производится переход к элементу, расположенному на левой ветви р(i).

c) р [ i ] < q – производится переход к элементу, расположенному на правой ветви р [ i ].

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

Построение В+ дерева

 

При выполнении этой операции руководствуются основным правилом: изначально все узлы кроме последнего содержат один дополнительный элемент (то есть m +1 потомков в сумме), который будет использован для построения внутренних узлов.

Рассмотрим алгоритм на примере. Пусть количество потомков для каждого листового узла не более 4, то есть степень дерева m = 5. На вход подана последовательность чисел от 1 до 24. Разобьём их на блоки по приведенному правилу:

1|2|3|4|5 6|7|8|9|10 11|12|13|14|15 16|17|18|19|20 21|22|23|24

Из слоя листовых узлов строим следующий уровень путём вынесения туда лишних (в данном случае пятых) элементов на уровень выше. У четырех из пяти блоков такие элементы есть. Это – 5, 10, 15 и 20. Полученный новый уровень разбиваем в соответствии с тем же правилом.

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

5|10|15 20 1|2|3|4 6|7|8|9 11|12|13|14 16|17|18|19 21|22|23|24

Продолжаем процесс, пока не получим корень.

15 5|10 20 1|2|3|4 6|7|8|9 11|12|13|14 16|17|18|19 21|22|23|24

Осталось добавить ссылки и получится готовое В-дерево.