Структуры и алгоритмы обработки данных

· остаток второй последовательности (19, 25) просто копируется в выходной набор с получением окончательного результата: (5, 8, 9, 11, 17, 19, 25)

В общем виде алгоритм слияния можно представить следующим образом. Пусть А={ai} и B={bj} - две исходные упорядоченные последовательности, R - результирующая последовательность.

1. сравниваем а1 и b1, если а1 < b1, то записываем а1 в R, иначе - b1 в R

2. если в уменьшившемся наборе остались числа, то сравниваем его минимальный элемент с минимальным элементом другого набора и записываем наименьший из них в R

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

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

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

1. в исходном наборе выделяются две подряд идущие возрастающие подпоследовательности (серии)

2. эти подпоследовательности (серии) сливаются в одну более длинную упорядоченную последовательность так, как описано выше

3. шаги 1 и 2 повторяются до тех пор, пока не будет достигнут конец входного набора

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

Пример. Пусть имеется входной неупорядоченный набор чисел:

24, 08, 13, 17, 06, 19, 20, 11, 07, 55, 33, 22, 18, 02, 40

Этап 1. Выделяем в нем серии (показаны скобками) и попарно сливаем их:

(24), (08, 13, 17), (06, 19, 20), (11), (07, 55), (33), (22), (18), (02, 40)

(24) + (08, 13, 17) = (08, 13, 17, 24)

(06, 19, 20) + (11) = (06, 11, 19, 20)

(07, 55) + (33) = (07, 33, 55)

(22) + (18) = (18, 22)

Новый набор чисел:

08, 13, 17, 24, 06, 11, 19, 20, 07, 33, 55, 18, 22, 02, 40

Этап 2. Выделяем в новом наборе серии и попарно сливаем их (число серий уменьшилось):

(08, 13, 17, 24), (06, 11, 19, 20), (07, 33, 55), (18, 22), (02, 40)

(08, 13, 17, 24) + (06, 11, 19, 20) = (06, 08, 11, 13, 17, 19, 20, 24)

(07, 33, 55) + (18, 22) = (07, 18, 22, 33, 55)

Новый набор:

06, 08, 11, 13, 17, 19, 20, 24, 07, 18, 22, 33, 55, 02, 40

Этап 3. Выделяем в новом наборе серии (всего три) и сливаем их:

(06, 08, 11, 13, 17, 19, 20, 24), (07, 18, 22, 33, 55), (02, 40)

(06, 08, 11, 13, 17, 19, 20, 24) + (07, 18, 22, 33, 55) = (06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55)

Новый набор и его две серии:

(06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55), (02, 40)

Этап 4. После слияния этих двух серий получим полностью упорядоченный набор:

02, 06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 40, 55

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

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

Для устранения этого недостатка можно поступить следующим образом:

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

· каждый фрагмент отдельно загружается в ОП и сортируется каким-нибудь классическим улучшенным методом (например - алгоритмом быстрой сортировки)

· каждый отсортированный фрагмент рассматривается как серия и сохраняется во вспомогательном файле; в простейшем случае достаточно двух вспомогательных файлов, в которые серии сбрасываются поочередно (нечетные серии - в один файл (A), четные - в другой (B)).

Эти действия носят подготовительный характер.

После этого начинается 2-ой этап сортировки:

· выполняется объединение первых серий из разных файлов, т.е. серий 1 и 2, и результат записывается в третий вспомогательный файл С

· выполняется объединение вторых серий из разных файлов, т.е. серий 3 и 4, и результат записывается во вспомогательный файл D

· выполняется объединение третьих серий из разных файлов, т.е. серий 5 и 6, и результат записывается опять в файл С

· серии 7 и 8 после объединения записываются в файл D и т.д.

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

Для программной реализации данного метода сортировки необходимы:

· достаточно большой массив в ОП для реализации 1-го этапа

· пять файлов, из которых один исходный и 4 вспомогательных.

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



Наоборот, если требуется ускорить сортировку за счет дополнительной дисковой памяти, то вместо 4-х вспомогательных файлов можно использовать 6,8,10 и т.д. Ускорение работы происходит за счет того, что объединяются не 2 серии, а 3, 4 или 5 и т.д.

5.8 Практические задания

Задание 1. Разработать программу для имитации обработки простейшего Б-дерева второго порядка. Программа должна выполнять следующие действия:

· построение Б-дерева для заданного набора вершин, начиная с пустого дерева

· добавление отдельной вершины

· поиск заданной вершины

· удаление заданной вершины

· вывод Б-дерева в наглядном виде

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

Задание 2. Разработать программу сортировки файлов методом естественного слияния. Для простоты этап предварительной сортировки фрагментов для получения начальных серий не реализуется. Должны использоваться 5 файлов - входной и 4 вспомогательных. Исходный набор заполняется случайными числами в диапазоне от 1 до 1 миллиона.

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

1. В чем состоят особенности задач внешнего поиска и сортировки?

2. Какой критерий является основным для алгоритмов внешнего поиска и сортировки?

3. Для решения каких задач используется структура данных Б-дерево?

4. Что называется страницей Б-дерева?

5. Почему страничная организация Б-дерева является эффективной для решения задачи внешнего поиска?

6. Каким условиям должно удовлетворять Б-дерево?

7. Какими свойствами обладает Б-дерево как дерево поиска?

8. Как оценивается эффективность использования Б-деревьев для задач внешнего поиска?

9. Какие данные должна содержать страница Б-дерева?

10. Какие описания необходимы для определения Б-дерева как структуры данных?

11. Какие шаги включает алгоритм поиска в Б-дереве?

12. Какие основные шаги включает алгоритм добавления вершины в Б-дерево?

13. Что происходит при попытке добавления новой вершины на полностью заполненную страницу Б-дерева?

14. К чему может привести процесс расщепления полной страницы Б-дерева при добавлении новой вершины?

15. В каких случаях высота Б-дерева может увеличиться на единицу?

16. Приведите практический пример добавления вершины в простейшее Б-дерево.

17. Какие особенности возникают при программной реализации алгоритма добавления новой вершины в Б-дерево?

18. Почему при добавлении новой вершины в Б-дерево необходимо запоминать путь от корневой страницы к терминальной?

19. Какие параметры использует рекурсивная подпрограмма добавления новой вершины в Б-дерево?

20. Приведите схему рекурсивной подпрограммы добавления новой вершины в Б-дерево.

21. Что должна делать главная программа при добавлении новой вершины в Б-дерево?

22. Какие основные шаги включает алгоритм удаления вершины из Б-дерева?

23. Как обрабатывается удаление вершины из Б-дерева для терминальной и нетерминальной страницы?

24. Как находится элемент-заменитель для удаляемой из Б-дерева вершины?

25. Какая ситуация может возникнуть после удаления вершины с одной из страниц Б-дерева?

26. За счет чего сохраняется необходимая структура Б-дерева после удаления вершины?

27. Зачем и как выполняется перераспределение вершин между двумя соседними страницами при удалении вершины из Б-дерева?

28. Зачем и как выполняется объединение двух страниц при удалении вершины в Б-дереве?

29. К каким последствиям может привести процесс слияния соседних страниц при удалении вершин из Б-дерева?

30. Приведите практический пример удаления вершины из простейшего Б-дерева.

31. Какие особенности имеет программная реализация удаления вершины из Б-дерева?

32. Какие параметры должна иметь рекурсивная подпрограмма удаления вершины из Б-дерева?

33. Приведите схему рекурсивной подпрограммы удаления вершины из Б-дерева.

34. В чем состоит принцип слияния двух упорядоченных последовательностей?

35. Какие шаги выполняет алгоритм слияния двух упорядоченных последовательностей?

36. Как используется алгоритм слияния последовательностей для сортировки данных?

37. Что такое серия и как это понятие используется при сортировке данных?

38. Как можно улучшить сортировку файлов методом естественного слияния?

39. В чем состоит первый этап внешней сортировки?

40. В чем состоит второй этап внешней сортировки?

41. Какие необходимы вспомогательные файлы при внешней сортировке и как они используются?

42. Как можно уменьшить число вспомогательных файлов, используемых при внешней сортировке?

43. За счет чего можно ускорить сортировку файлов?

44. Как влияет число вспомогательных файлов на эффективность внешней сортировки?

Основные термины и понятия

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

Балансировка дерева - перестановка вершин с целью сохранения "хорошей" структуры дерева

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

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

Внешняя сортировка - упорядочивание больших наборов данных с преимущественным хранением на дисковой памяти

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

Внутренняя сортировка - упорядочивание элементов массива, полностью располагающихся в оперативной памяти

Высота дерева - наиболее длинный путь от корневой вершины к терминальной

Граф - нелинейная структура данных, состоящая из элементов-вершин, между некоторыми из которых установлены определенные связи

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

Двунаправленный линейный список - разновидность списковой структуры, в которой каждый элемент имеет два указателя на каждого из своих соседей

Дерево - нелинейная структура данных, рекурсивно представимая в виде отдельных поддеревьев

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

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

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

Заголовок списка - дополнительный необязательный элемент в начале списка, который никогда не удаляется из списка

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

Карманная сортировка - один из специальных методов сортировки, применяемый для ключей с различными значениями в пределах от 1 до n

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

Матрица смежности - способ описания графа с помощью двухмерного массива N*N, ненулевые элементы которого соответствуют связанным вершинам

Метод Шелла - улучшенный метод сортировки массивов, основанный на многократном группировании элементов массива с уменьшающимся шагом и последующей сортировкой методом вставок

О-нотация - способ оценивания трудоемкости алгоритма в зависимости от объема обрабатываемых данных

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

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

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

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

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

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

Простейшие методы сортировки - алгоритмически простые методы сортировки массивов с трудоемкостью порядка n2

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

Сортировка выбором - простейший метод сортировки массивов, основанный на поиске в необработанном подмножестве наименьшего элемента

Сортировка обменом - простейший метод сортировки массивов, основанный на попарном сравнении и перестановке соседних элементов

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

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

Список смежности - способ описания графа в виде массива или главного списка вершин, с каждым элементом которого связан список смежных с нею вершин

Стек - линейная структура данных с односторонним добавлением и удалением элементов

Улучшенные методы сортировки - алгоритмически достаточно сложные методы сортировки массивов с трудоемкостью порядка n*logn

Универсальные методы сортировки - группа методов сортировки массивов, не требующих никакой дополнительной информации о сортируемых наборах и никакой дополнительной памяти

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

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

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

Литература

1. Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. - М.: Изд. дом "Вильямс", 2000 г.

2. Кнут Д. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. - М.: Изд. дом "Вильямс", 2000 г.

3. Вирт Н. Алгоритмы и структуры данных

4. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. - М.: Изд. дом "Вильямс", 2001 г.

5. Кормен Т. и др. Алгоритмы: построение и анализ. - МЦНМО, 2000 г.

6. Топп У., Форд У. Структуры данных в С++. - М.: ЗАО "Издательство БИНОМ", 2000 г.

7. Хэзфилд Р., Кирби Л. и др. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений. - К.: Издательство "ДиаСофт", 2001 г.

Размещено на Allbest.ru