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

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

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

3 Дан массив 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 Задачей сортировки по неубыванию (невозрастанию) является нахождение перестановки элементов массива, при которой ключи располагаются в порядке неубывания (невозрастания). В результате работы алгоритма и применения перестановки получается отсортированный массив. Формулировка задачи 4

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

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

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

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

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

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

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

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

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

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

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

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