Пирамидальная сортировка

 Рассмотрим пирамидальную сортировку или по другому сортировку кучей. Данный тип сортировки хорош тем что является быстрям и не требует большого объема дополнительной памяти для своей работы. В отличии от например алгоритмов быстрой сортировки или сортировки слянием. т.к. может работать на той же памяти в которой находится сортируемый массив. за исключением может быть только дополнительной памяти хранения одного элемента для обмена между ячейками. Вычислительная сложность алгоритма O(n*log(n)) где n это количество элементов в сортируемом массиве. Также он достаточно не сложно реализуется итеративным методом для массива произвольной длинны что также большой плюс для экономии и контроля памяти а следовательно хорошо подходит для работы на устройствах с небольшим количеством памяти например для микроконтроллеров. Любой массив любой длинны можно представить ввиде пирамиды или двоичного дерева. У пирамиды есть верхушка, это первый элемент массива. Уровнем ниже располагаются два потомка первого элемента, левый и правый и это второй и третий элементы массива. Ещё ниже уровнем есть следующих 4 элемента массива которые являются потомками элеменов уровнем выше, это будут 4,5,6,7й элементы массива. И так далее. У каждого элемента (кроме самых нижних) есть максимум два потомка и один родитель (кроме самого верхнего). левый потомок, в массиве, находиться по формуле i_left=2*i+1 а правый по формуле i_right=2*i+2 где i это текущий индекс родителя в массиве. Индекс (в массиве) родителя одного из (любого) потомков может быть найден по формуле i = (int)(n / 2) - 1 где n это индекс одного из потомков (левого или правого). Сортировка состоит из двух больших этапов. На первом этапе, вся пирамида преобразуется в сортирующее "дерево" т.е. "кучу". Сортирующее "дерево" т.е. куча, отличается от обычного двоичного дерева в д.с. пирамиды тем что у кучи каждый родитель старше потомков т.е. больше или меньше их, в зависимости от направления сортировки. Допустим в следующих примерах будет больше. Исходя из этого следует одно интересное свойство кучи, а имеено, элемент на её верхушке всегда самый старший т.е. в д.с. самый большой. Это свойство и используется для сортировки. После того как пирамида преобразована в кучу можно осуществлять бинарный поиск самого большого числа за колличество уровней пирамиды минус один т.к. нижний уровень состоит только из потомков. Это быстрее чем перебор по всем элементам т.к. уровней пирамиды меньше чем всех элементов. Двоичный поиск или также поразрядное уроавновешивание мы уже рассматривали в статье про двухбитный АЦП на ATtiny2313 Очевидно что такой способ поиска быстрее чем полный последовательный перебор. На втором большом этапе сначала первый самый большой элемент меняется местами с последним элементом массива. Далее этот последний элемент как бы исключается из пирамиды т.к. он уже отсортирован и осталасть вся остальная чать. Остальная чать перестала быть кучей, в резултате этой операции, поэтому куча восстанавливается в резултате чего первый элемент снова становиться самым большим из оставшихся. Этот элемент помещается на предпоследнее место массива. Это место исключается из пирамиды и так повторяется для всех элементов до самого первого в резултате массив становиться отсортированным. теперь можно рассмотреть данный алгоритм подробнее. В нем можно выделить одну часто используемую процедуру на двух этапах. Это процедура в резултате которой на верху пирамиды оказывается самый большой элемент. Она похожа на сортировку пузырьком, только не по всем элементам массива а по уровням пирамиды. Начинается эта процедура с самого верхнего элемента пирамиды или подпирамиды. Далее из тройки родитель, левый потомок, правый потомок. Выбирается наибольший Если родитель наибольший то процедура завершается, если левый потомок больше то его значение меняется местами со значением родителя и происходит переход на следующей итерации к левому потомку который теперь считается родителем. Если больше был правый потомок то его значение меняется местами со значением родителя и переход происходит к правому потомку далее операции повторяются с новым родителем и так до последнего уровня пирамиды или подпирамиды. На первом этапе эта процедура применяется для всех подпирамид элементов начиная с последнего элемента предпоследнего ряда пирамиды и заканчивая самам первым элементом пирамиды. После чего вся пирамида становиться кучей. Построение кучи начинается от родителя самого последнего в массиве элемента. А точнее это самый простой способ определить начало старта построения дерева. Заканчивается построение на вершине пирамиды. и идет как бы от низа к вершине. Поэтому цикл построения дерева будет таким: for(int i = (int)(ARRAY_LENGTH / 2) - 1; i >= 0; i--)  

 В теле цикла будет процедура всплывания самого большого/маленького (зависит от направления сортировки) элемента в том диапазоне который мы ограничиваем на данной итерации. #include <stdio.h> // всплывание наибольшего элемнта на верх подпирамиды где // array - сортируемый массив // i_top - индекс верхнего элемента подпирамиды которая делается сортирующей // i_bottom - индекс нижнего элемента подпирамиды которая делается сортирующей int surfacing(int* array, int i_top, int i_bottom) { int i = i_top; // индекс верхнего элемента подпирамиды которая делается сортирующей int i_max = i_top; // максимальный элемент в тройке родитель-потомки int buffer = 0; // для обмена значений между родителем и потомком while (1) { int i_left = 2*i+1; // левый потомок int i_right = 2*i+2; // правый потомок // поиск большего в тройке родитель и два потомка if ( i_left < i_bottom && array[i_left] > array[i_max] ) { i_max = i_left; } if ( i_right < i_bottom && array[i_right] > array[i_max] ) { i_max = i_right; } if( i == i_max ) return 0; // обмен и всплытие большего из потомков на уровень родителя buffer = array[i]; array[i] = array[i_max]; array[i_max] = buffer; i = i_max; // переход на следующий уровень к наибольшему потомку } } // пирамидальная сортировка void heapSort(int* array, int array_length) { int buffer = 0; // для обмена значений между родителем и потомком // 1. построение сортирующего дерева (кучи) for(int i = (int)(array_length / 2) - 1; i >= 0; i--) { surfacing(array, i, array_length-1); } // 2. сортировка for(int i = array_length - 1; i > 0; i--) { // обмен верхнего, являющегося самым большим, элемента с текущим buffer = array[i]; array[i] = array[0]; array[0] = buffer; // всплытие следеющего по размеру элемента путем постоения кучи из неотсортированной части пирамиды surfacing(array, 0, i); } }  

 Проверка функций пирамидальной сортировки // gcc main.c heap_sort.c -o heap_sort_example #include <stdio.h> #define ARRAY_LENGTH 15 int array[ARRAY_LENGTH] = {66, 220 ,340, 100, 77, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1}; void surfacing(int* array, int i_top, int i_bottom); void heapSort(int* array, int array_length); int main() { printf("array = "); for (int i=0; i<ARRAY_LENGTH; i++) { printf("%d ",array[i]); } printf("\n"); heapSort(array, ARRAY_LENGTH); printf("sorted array = "); for (int i=0; i<ARRAY_LENGTH; i++) { printf("%d ",array[i]); } printf("\n"); return 0; }  

Для проверки можно сделать два файла с расширением си. В одном будут функции сортировки а в другом ппрверка их работы. Для того чтобы откомпилировать программу можно воспользоваться компилятором gcc и командой gcc main.c heap_sort.c -o heap_sort_example или же можно сделать простой Make файл для того чтобы запускать компиляцию командой Make # Имя компилятора CXX = gcc # Имя итогового исполняемого файла TARGET = heap_sort_example # Список исходных файлов SRCS = main.c heap_sort.c # Правило по умолчанию (просто вызов 'make') all: $(TARGET) # Правило сборки проекта $(TARGET): $(SRCS) $(CXX) $(SRCS) -o $(TARGET)  

 Если откомпилировать программу и запустить то мы видим что сортировка тестового массива происходит правильно.

Визуализация Heap Sort со случайным массивом

Адрес биткоин кошелька для поддержки блога - bc1qlhrmmkh77x2lzhqe4lt9qwkglswj64tsqt2l5g