Введение
Сравнительный алгоритм сортировки
В информатике адаптивная сортировка кучей — это сравнительный алгоритм сортировки из семейства адаптивных алгоритмов сортировки. Это вариант сортировки кучей, который показывает лучшие результаты, когда данные уже частично упорядочены. Алгоритм, опубликованный Христосом Левкопулосом и Олой Петерссоном в 1992 году, использует новую меру предварительной упорядоченности, Osc, определяемую как количество осцилляций. В отличие от традиционной сортировки кучей, которая помещает все данные в кучу, адаптивная сортировка кучей помещает в кучу только часть данных, что значительно сокращает время выполнения при высокой степени предварительной упорядоченности. Обычно алгоритм включает следующие четыре шага. Построение Max-кучи (Min-кучи): поместите все данные в кучу так, чтобы каждый узел был больше или равен (меньше или равен для Min-кучи) каждому из его дочерних узлов. Поменяйте местами первый и последний элементы кучи. Удалите последний элемент из кучи и поместите его в конец списка. Восстановите структуру кучи, чтобы первый элемент оказался на своем месте. Повторяйте шаги 2 и 3, пока в куче не останется только один элемент. Поместите этот последний элемент в конец списка и выведите отсортированный список. Ниже представлена реализация на C/C++, которая строит Max-кучу и сортирует массив после ее построения. /* Пример кода сортировки кучей на C/C++, сортирующий массив по возрастанию */ // Функция для построения Max-кучи (бинарного дерева) void heapify(int array[], int start, int end) { int parent = start; int child = parent * 2 + 1; while (child <= end) { if (child + 1 <= end) // если есть два дочерних узла { if (array[child + 1] > array[child]) { child++; // выбрать больший дочерний узел } } if (array[parent] > array[child]) { return; // если родительский узел больше, куча уже построена } if (array[parent] < array[child]) // если дочерний узел больше родительского { swap(array[parent], array[child]); // поменять родительский и дочерний узлы parent = child; child = child * 2 + 1; // продолжить цикл, сравнить дочерний узел с его дочерними узлами } } } // Функция сортировки кучей void heap_sort(int array[], int len) { for (int i = len / 2 - 1; i >= 0; i--) // Шаг 1: построение Max-кучи { heapify(array, i, len - 1); } for (int i = len - 1; i >= 0; i--) // Шаг 4: повторение шагов 2 и 3 до завершения { swap(array[0], array[i]); // Шаг 2: поместить максимальный элемент в конец массива heapify(array, 0, i - 1); // Шаг 3: удалить максимальный элемент из кучи и восстановить ее } } int main() { // Массив для сортировки int array[] = {42, 1283, 123, 654, 239847, 45, 97, 85, 763, 90, 770, 616, 328, 1444, 911, 315, 38, 5040, 1}; int array_len = sizeof(array) / sizeof(*array); // Длина массива heap_sort(array, array_len); return 0; }
In computer science, adaptive heap sort is a comparison based sorting algorithm of the adaptive sort family. It is a variant of heap sort that performs better when the data contains existing order. Published by Christos Levcopoulos and Ola Petersson in 1992, the algorithm utilizes a new measure of presortedness, Osc, as the number of oscillations. Instead of putting all the data into the heap as the traditional heap sort did, adaptive heap sort only take part of the data into the heap so that the run time will reduce significantly when the presortedness of the data is high. It usually involves the following four steps. Build a Max Heap(Min Heap): put all the data into the heap so that all nodes are either greater than or equal (less than or equal to for Min Heap) to each of its child nodes. Swap the first element of the heap with the last element of the heap. Remove the last element from the heap and put it at the end of the list. Adjust the heap so that the first element ends up at the right place in the heap. Repeat Step 2 and 3 until the heap has only one element. Put this last element at the end of the list and output the list. The data in the list will be sorted. Below is a C/C++ implementation that builds up a Max Heap and sorts the array after the heap is built. /*
A C/C++ sample heap sort code that sort an array to an increasing order
*/
// A function that build up a max heap binary tree
void heapify(int array[], int start, int end)
{
int parent = start;
int child = parent * 2 + 1;
while (child <= end)
{ if (child + 1 <= end) // when there are two child nodes
{
if (array[child + 1] > array[child])
{
child ++; //take the bigger child node
}
}
if (array[parent] > array[child])
{
return; //if the parent node is greater, then it's already heapified
}
if (array[parent] < array[child]) // when child node is greater than parent node
{
swap (array[parent], array[child]); // switch parent and child node
parent = child;
child = child * 2 + 1; //continue the loop, compare the child node and its child nodes
}
}
}
// heap sort function
void heap sort (int array[], int len)
{
for (int i = len/2 1; i >= 0; i ) //Step 1: build up the max heap
{
heapify(array, i, len);
}
for (int i = len 1; i >= 0; i ) //Step 4: repeat step 2 and 3 till finished
{
swap(array[0], array[i]); // Step 2: put the max at the end of the array
heapify (array, 0, i 1); // Step 3: remove the max from the tree and heapify again
}
}
int main
{
//the array that will be sorted
int array[] = {42, 1283, 123, 654, 239847, 45, 97, 85, 763, 90, 770, 616, 328, 1444, 911, 315, 38, 5040, 1};
int array len = sizeof(array)/sizeof(*array); //length of the array
heap sort (array, array len);
return 0;
}
Меры предварительного сортирования
Меры предсортированности оценивают существующий порядок в заданной последовательности. Эти меры предсортированности определяют объем данных, которые будут помещены в кучу в процессе сортировки, а также нижнюю границу времени выполнения.
Недостатки
Несмотря на десятилетия исследований, сохраняется разрыв между теорией адаптивной сортировки кучей и её практическим применением. Алгоритм, использующий картезианские деревья и манипуляции с указателями, обладает низкой эффективностью кэширования и высокими требованиями к памяти, что негативно сказывается на производительности реализаций.