озвучка курсача. Интроспективная сортировка

• Название: Интроспективная сортировка
• Дата: 19.09.2022
• Размер: 28.61 Kb.
• Имя файла: озвучка курсача.docx
• Тип: Документы; #685551

Интроспективная сортировка

У нас есть массив из элементов для начала вычисляется глубина рекурсии по формуле n log(n) далее проверяется массив если количество элементов в массиве больше чем 16 тогда вычисляется элемент pivot на основе быстрой сортировки используя медиану из 3 то есть проверяется начало середина и конец массива среднее значение сохраняется в переменную pivot, далее формируется два под массива где будет элементы меньше pivot и больше pivot. При этом глубина рекурсии уменьшится на один. После этого подмассив в котором значения меньше pivot, смотрим что если количество элементов меньше 16 значит мы все сортируем вставками. В под массиве в котором значения больше pivot, и кол-во элементов больше 16 сортируем быстрой сортировкой. Если же элементов меньше 16 то вставкой. Но если бы глубина рекурсии упала до 0, то все остальные операции производились пирамидальной сортировкой для того чтобы не вырождать квадратичное поведение быстрой сортировки.

Быстрая сортировка

Метод основан на подходе "разделяй-и-властвуй". Общая схема такова:

1. 
   из массива выбирается некоторый опорный элемент a[i],
   
2. 
   запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,
   
3. 
   теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого,
   
   
4. 
   для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.
   

Пирамидальная

Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.

Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду. Затем берем предпоследний элемент и т.д.