Tree Sort Сортировка двоичным деревом

1. Tree Sort

TREE SORT
Сортировка двоичным деревом

2. Что это?

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

3. Алгоритм

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

4. В чем недостаток алгоритма?

При физическом развёртывании древовидной структуры в
памяти требуется не менее чем 4n ячеек дополнительной
памяти.
Каждый узел содержит:
• ссылки на элемент исходного массива;
• на родительский элемент;
• на левый и правый лист.
Однако, существуют способы уменьшить
требуемую дополнительную память.

5. Эффективность

Процедура добавления объекта в бинарное дерево
имеет среднюю алгоритмическую сложность порядка
O(log(n)).
Однако, сложность добавления объекта в
разбалансированное дерево может достигать
O(n), что может привести к общей сложности
порядка O(n²)!!!

6. В чем причина роста сложности алгоритма?

Общее быстродействие метода O(nlogn). Почему?
Поведение неестественно, устойчивости, вообще говоря, нет.
Требуется n операций на создание первоначального
дерева, каждый по log n сравнений для выбора
наименьшего и наибольшего.

7. Результаты работы алгоритма

Количество
Размер массива итераций
100
200
300
400
500
600
700
800
900
1000
1100
1200
1300
1400
1500
1600
1700
1800
1900
2000
2100
2200
2300
2400
2500
2600
2700
2800
2900
3000
5049
20099
45149
80199
125249
180299
245349
320399
405449
500499
605549
720599
845649
980699
1125749
1280799
1445849
1620899
1805949
2000999
2206049
2421099
2646149
2881199
3126249
3381299
3646349
3921399
4206449
4501499
Время (ннс)
1805108
981807
661719
838690
1292147
581697
592982
779700
777648
908965
1116202
981293
1467067
1327029
1579918
1881539
2100060
1762020
1818958
1482969
1299329
1920011
1694309
1580944
3675362
1885643
3566614
2737157
2491962
2380650
3100
3200
3300
3400
3500
3600
3700
3800
3900
4000
4100
4200
4300
4400
4500
4600
4700
4800
4900
5000
4806549
5121599
5446649
5781699
6126749
6481799
6846849
7221899
7606949
8001999
8407049
8822099
9247149
9682199
10127249
10582299
11047349
11522399
12007449
12502499
2873605
3276278
2746391
3143934
3643558
3844639
3674849
4085730
3987242
4979307
4787460
5425070
5440458
5447127
5804148
6572050
6969594
7145027
6494079
6883417

8. График зависимости затраченного времени от размера массива.

8000000
7000000
6000000
5000000
4000000
Время (ннс)
3000000
2000000
1000000
0
1
3
5
7
9
11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49

9. График зависимости количества итераций от размера массива.

14000000
12000000
10000000
8000000
Количество итераций
6000000
4000000
2000000
0
1
3
5
7
9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49

10. Применение

TreeSort обычно применяют там, где –
• построенное дерево можно с успехом применить для таких задач;
• данные уже построены в 'дерево‘;
• данные можно считывать непосредственно в дерево;
• при потоковом вводе с консоли или из файла.

11. Источники

• http://cppalgo.blogspot.ru/2010/09/treesort.html
• https://ru.wikipedia.org
• http://www.martinbroadhurst.com/cpp-sorting.html
• Описание метода 'древесной сортровки' можно найти
у H. Вирта в книге 'Алгоритмы + Структуры Данных =
Программы'