Пирамидальная сортировка
Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов.
Выполнение алгоритма разбивается на два этапа:
Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбирается путь через меньший элемент.
Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду. Затем берем предпоследний элемент и т.д.
В процессе работы программы происходит последовательное создание и заполнение случайными числами 1000 массивов для каждой заданной длины. Далее происходит сортировка данных.
Помимо этого, фиксируется количество операций (перестановок и сравнений) в специально созданные переменные.
Полный код программы представлен в приложении Г. Результат работы программы представлен на рисунке 2.4.1.
Рисунок 2.4.1 - Результат работы программы 4
В консольном выводе представляется размерность каждой тысячи массивов, среднее значение от суммы операций, а также среднее время выполнения сортировки.
Таблица 7 представляет собой таблицу со значениями длины массивов и средними значениями количества операций.
Таблица 7 - Средние значения количества операций пирамидальной сортировки
Размерность массивов |
Среднее количество операций |
1 |
3,000 |
2 |
8,516 |
3 |
20,438 |
4 |
32,503 |
5 |
50,518 |
10 |
148,375 |
15 |
393,885 |
20 |
393,885 |
25 |
534,642 |
30 |
675,144 |
50 |
1314,269 |
75 |
2189,083 |
100 |
3124,768 |
250 |
9418,430 |
500 |
21316,043 |
Далее необходимо построить график зависимости количества операций от длины массивов. График представлен на рисунке 2.4.2.
Рисунок 2.4.2 - График зависимости количества операций от длины массивов
Таблица 8 представляет собой таблицу со значениями длины массивов и среднего времени выполнения сортировки (среднего времени выполнения всех сравнений и перестановок).
Таблица 8 - Значения среднего времени выполнения операций пирамидальной сортировки
Размерность массивов |
Затраченное время (с) |
1 |
0,000000 |
2 |
0,000000 |
3 |
0,000000 |
4 |
0,000000 |
5 |
0,000000 |
10 |
0,000000 |
15 |
0,000001 |
20 |
0,000001 |
25 |
0,000002 |
30 |
0,000002 |
50 |
0,000006 |
75 |
0,000010 |
100 |
0,000015 |
250 |
0,000043 |
500 |
0,000096 |
Далее необходимо построить график зависимости затраченного на выполнение сортировки времени от длины массива. График представлен на рисунке 2.4.3.
Рисунок 2.4.3 - График зависимости затраченного времени от длины массивов
На основе полученных графиков, построим графики зависимостей y=n, y=n*log(n), y=n^2, y=n^3. Графики представлены на рисунке 2.4.4.
Рисунок 2.4.4 – Графики зависимости для пирамидальной сортировки
Проанализировав полученные результаты, можно сделать вывод о том, что график количества операций лежит между графиками y=n*log(n) и y=n^2. А следовательно, лучшее время для пирамидальной сортировки O(n*log(n)), а худшее - О(n^2).