СОРТИРОВКА ДЕРЕВОМ Выполнил: ст-т гр. ХХХХ.

Презентация:



Advertisements
Похожие презентации
Задание бинарных деревьев с помощью массивов Обходы деревьев.
Advertisements

Алгоритмы внешней сортировки (часть I, базовые понятия и алгоритмы) Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных.
Дистанционная подготовка к Всероссийской олимпиаде по информатике Преподаватель: к.ф.-м.н., заведующий кафедрой ВТиКГ ДВГУПС Пономарчук Юлия Викторовна.
Б-деревья Лекция 19. Б-деревья Б-деревья – сбалансированные деревья, обеспечивающие эффективное хранение информации на дисках и других устройствах с прямым.
Деревья и их представление в STL Презентацию подготовила Чиркова Ольга, 2 подгруппа, группа 271ПИ.
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ Лекции для студентов-заочников 2 курса, специальность (Прикладная информатика)
МЕТОДЫ СОРТИРОВКИ. Сортировка - расположение элементов множества в порядке расположения некоторого ключа. ОГРАНИЧЕНИЯ: 1. Рассматриваются внутренние сортировки.
Одномерные массивы Сортировка одномерных массивов.
1 Сложность, сортировка, поиск Работа по дисциплине «Алгоритмы и структуры данных» Выполнена Садукевич А.В., 271ПИ.
Механизмы поиска в БД Структуры индексов. Основные виды индексов Простые индексы для упорядоченных файлов Вторичные индексы для неупорядоченных файлов.
Поиск информации Задача поиска: где в заданной совокупности данных находится элемент, обладающий заданным свойством? Большинство задач поиска сводится.
Логическое программировыание Презентация 5 Списки в Прологе.
Другие формы рекурсии II Функциональное программирование Григорьева И.В.
Алгоритмы сортировки и поиска Выполнил Блинов В.А.
Необхідність структурування даних. Послідовне і зв ' язне розподілення даних в пам ' яті ЕОМ. Статичні і динамічні структури даних.
Лекция 9 Б-деревья План лекции 1.Структуры данных на диске 2.Определение Б-дерева. 3.Высота Б-дерева. 4.Поиск в Б-дереве 5.Создание пустого дерева. 6.Разбиение.
Какие типы данных изображены на рисунках? Линейчатый Круговой.
Дерево это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами.
Алгоритмы сортировки Лектор: к.т.н., доцент кафедры вычислительной техники Токарева Ольга Сергеевна Алгоритмы и технология их разработки.
1 Исследование алгоритмов решения задачи k коммивояжеров Научный руководитель, проф., д.т.н. Исполнитель, аспирант Ю.Л. Костюк М.С. Пожидаев Томский государственный.
Транксрипт:

СОРТИРОВКА ДЕРЕВОМ Выполнил: ст-т гр. ХХХХ

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

Дан массив A из n элементов а 1, а 2, …, а n Будем считать, что с каждым элементом а i (помимо другой информации, не влияющей на сортировку) связан ключ k i K. На множестве ключей K задано отношение порядка линейного (или совершенного) упорядочивания, для которого были бы выполнены следующие условия: 1) закон трихотомии: для любых x, y K либо x y, либо x=y; 2) транзитивность: для любых x, y,z K если x

Задачей сортировки по неубыванию (невозрастанию) является нахождение перестановки элементов массива, при которой ключи располагаются в порядке неубывания (невозрастания). В результате работы алгоритма и применения перестановки получается отсортированный массив. Формулировка задачи 4

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

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

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

Сортировка выбором Сортировка пузырьком Сортировка перемешиванием Сортировка вставками Сортировка слиянием Сортировка с помощью двоичного дерева (англ. Tree sort ) Сортировка с помощью двоичного дереваангл. Сортировка подсчётом Блочная сортировка 8 Список алгоритмов сортировки

Универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей.алгоритм сортировкидвоичного дерева поиска Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например с файла, сокета или консоли).потока 9 Сортировка деревом

Двоичным(бинарным) деревом назовем упорядоченную структуру данных, в которой каждому элементу - предшественнику или корню (под)дерева - поставлены в соответствие по крайней мере два других элемента (преемника). Причем для каждого предшественника выполнено следующее правило: левый преемник всегда меньше, а правый преемник всегда больше или равен предшественнику. Вместо 'предшественник' и 'преемник' также употребляют термины 'родитель' и 'сын'. Все элементы дерева также называют 'узлами'. 10 Определения

Нарисуем "полное двоичное дерево" - картинку, в которой снизу один кружок, из него выходят стрелки в два других, из каждого - в два других и так далее: Будем говорить, что стрелки ведут "от отцов к сыновьям": у каждого кружка два сына и один отец (если кружок не верхний). 11 Пример двоичного дерева

При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами, таким образом вставляя на место. Если элемент >= корня - он идет в правое поддерево, сравниваем его уже с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым, и так далее, пока есть сыновья, с которыми можно сравнить. Рассмотрим процесс построения дерева из последовательности: : 12 Процесс построения дерева

Если мы будем рекурсивно обходить дерево по правилу "левый сын - родитель - правый сын", то, записывая все встречающиеся элементы в массив, мы получим упорядоченное в порядке возрастания множество. На этом основана идея сортировки деревом. Более подробно правило обхода можно сформулировать так: обойти левое поддерево - вывести корень - обойти правое поддерево, где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается с узлом-родителем и выдает очередной элемент, если у узла нет сыновей. 13 Сортировка деревом

1. Построение двоичного дерева. 2. Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей. 14 Этапы сортировки :

сравнить ключ добавляемого поддерева (К) с ключом корневого узла (X). Если K>=X, рекурсивно добавить новое дерево в правое поддерево. Если K

Основной недостаток сортировки деревом - большие требования к памяти под дерево. Очевидно, нужно n места под ключи и, кроме того, память на 2 указателя для каждого из них. Поэтому TreeSort обычно применяют там, где - построенное дерево можно с успехом применить для других задач: данные уже построены в 'дерево'. данные можно считывать непосредственно в дерево. Например, при потоковом вводе с консоли или из файла. 16 Недостатки метода