Dyzzet|
C++ Data Science
Алгоритмы
Темы · Блог · YouTube
19 июля 2022
Пирамидальная сортировка. Интерактивная анимация
Авторы: Dyzzet, joparino

Пирамидальная сортировка (сортировка кучей, heapsort) — сортировка, которая использует логическое представление массива в виде кучи. Куча — по крайней мере в этом варианте, который называется max-heap — это двоичное (бинарное) дерево, каждый элемент которого меньше своего родителя.

heapsort() сперва вызывает функцию heapify(), которая особым образом перестраивает массив: превращает его в кучу. Изначально элементы массива располагаются так: нулевой элемент — корень, следующие два элемента — потомки корневого узла и т. д.

Поскольку самый большой элемент — корневой, то есть нулевой элемент массива, он обменивается с последним (последний элемент больше не будет перемещаться).

Но свойства кучи оказываются нарушенными, поэтому вызывается функция siftDown() (другие варианты термина sift down: bubble down, push down, fix down), которая эти свойства восстанавливает: «просеивает» элемент с вершины кучи до некоторой позиции так, чтобы в итоге восстановились свойства кучи. В альтернативном варианте элементы просеиваются наверх.

Код использует функцию parentIndex() для вычисления индекса родительского узла в куче по индексу узла \(p(i)=\left\lfloor\dfrac{i - 1}{2}\right\rfloor,\) leftChildIndex() — для вычисления индекса левого потомка: \(l(i)=2i+1,\) rightChildIndex() — для правого: \(r(i)=2i+2.\)

Читать далее →
16 января 2022
Асимптотики

16 апреля 2021
Быстрая сортировка. Вариант с указателем. Интерактивная анимация

Первый вариант быстрой сортировки

Реализация быстрой сортировки со следующими аргументами функции: указатель на начало массива и его размер. В предыдущей реализации нумерация элементов подмассива всегда велась относительно начала исходного массива, в рекурсивные вызовы передавались аргументы left и right, обозначающие границы подмассивов.

Как и ранее, подмассив, с которым работает конкретный рекурсивный вызов, выделен чёрным цветом и подчёркнут синей линией. Для большей наглядности показано data[0] (значение самого левого элемента текущего подмассива).

Читать далее →
2
1
© MMXI—MMXXIII. RSS. Поддержать сайт
Светлая тема / тёмная тема