АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Сортировка методом турнира с выбыванием

Читайте также:
  1. Алгоритм решения ЗЛП графическим методом
  2. Алгоритм решения систем линейных уравнений методом Жордана-Гаусса
  3. Анализ движения денежных средств прямым и косвенным методом
  4. Анализ методом деревьев событий и отказов
  5. Б.ВВП методом потока расходов
  6. Вибір оптимального варіанта СМ методом мікровартостей
  7. Визначення осмотичного тиску клітинного соку плазмолітичним методом
  8. Визначення параметрів емпіричної формули за методом найменших квадратів.
  9. Визначення площі листка ваговим методом
  10. Вимірювання кута фазового зсуву методом зрівноважуючого перетворення
  11. Вимірювання опору розчинів компенсаційним методом
  12. Вимірювання струмів методом ядерного магнітного резонансу (ЯМР)

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

10, 20, 3, 1, 5, 0, 4, 8

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

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

Рис.4.10. Построение дерева сортировки

В результате построения такого дерева наименьший элемент попадает сразу в корень. Далее начинается извлечение элементов из дерева. Извлекается значение из корня. Данное значение является первым элементом в результирующем массиве. Извлеченное значение помещается в отсортированный массив и заменяется в дереве на специальный символ.

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

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

Рис.4.11. Замена извлекаемого элемента на специальный символ
Рис.4.12. Повторное заполнение дерева сортировки
Рис.4.13. Извлечения элементов из дерева сортировки

В результате получим отсортированный массив

0, 1, 3, 4, 5, 8, 10, 20


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 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)