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

В информатике адаптивная пирамидальная сортировка — это на основе сравнения алгоритм сортировки из семейства адаптивных сортировок . Это вариант сортировки кучи , который работает лучше, когда данные содержат существующий порядок. опубликованный Кристосом Левкопулосом и Олой Петерссоном Алгоритм, в 1992 году, использует новую меру предварительной сортировки Osc в качестве числа колебаний. ^[1] Вместо того, чтобы помещать все данные в кучу, как это делалось при традиционной сортировке кучи, адаптивная сортировка кучи переносит в кучу только часть данных, так что время выполнения значительно сокращается при высокой предварительной сортировке данных. ^[1]

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

Сортировка кучей — это алгоритм сортировки, использующий двоичной кучи структуру данных . Этот метод рассматривает массив как полное двоичное дерево и создает Макс-кучу/Мин-кучу для сортировки. ^[2] Обычно это включает в себя следующие четыре шага.

Постройте Max-Heap(Min-Heap): поместите все данные в кучу так, чтобы все узлы были либо больше, либо равны (меньше или равны для Min-Heap ) каждому из его дочерних узлов.
Поменяйте местами первый элемент кучи с последним элементом кучи.
Удалите последний элемент из кучи и поместите его в конец списка. Настройте кучу так, чтобы первый элемент оказался в нужном месте в куче.
Повторяйте шаги 2 и 3, пока в куче не останется только один элемент. Поместите этот последний элемент в конец списка и выведите список. Данные в списке будут отсортированы.

Ниже представлена реализация C/C++, которая создает Max-Heap и сортирует массив после создания кучи.

/*A C/C++ sample heap sort code that sort an array to an increasing order*/// A function that build up a max-heap binary treevoid 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 functionvoid 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;}

Меры предварительной сортировки

Меры предварительной сортировки измеряют существующий порядок в заданной последовательности. ^[3] Эти меры предварительной сортировки определяют количество данных, которые будут помещены в кучу во время процесса сортировки, а также нижнюю границу времени выполнения. ^[4]

Колебания ( Osc )

Для последовательности $X=\langle x_{1},x_{2},x_{3},\dots ,x_{n}\rangle$ , Cross ( x _i ) определяется как количество ребер линейного графика X , которые пересекаются горизонтальной линией, проходящей через точку ( i, x _i ). Математически это определяется как ${\mathit {Cross}}(x_{i})=\{j\mid \min\{x_{j},x_{j+1}\}<x_{i}<\max\{x_{j},x_{j+1}\}{\text{ for }}1\leq j<n\}{\text{, for }}1\leq i\leq n$ . Колебание ( Osc ) X — это просто общее количество пересечений, определяемое как ${\mathit {Osc}}(x)=\textstyle \sum _{i=1}^{n}\displaystyle \lVert {\mathit {Cross}}(x_{i})\rVert$ . ^[1]

Другие меры

Помимо исходного измерения Osc, другие известные меры включают количество инверсий Inv , количество прогонов Runs , количество блоков Block и меры Max , Exc и Rem . Большинство этих различных измерений относятся к адаптивной пирамидальной сортировке. Некоторые меры доминируют над другими: каждый Osc-оптимальный алгоритм является оптимальным для Inv и оптимальным для выполнения; каждый Inv-оптимальный алгоритм является Max-оптимальным; и каждый блочно-оптимальный алгоритм является оптимальным Exc и оптимальным Rem. ^[4]

Алгоритм

Адаптивная пирамидальная сортировка — это вариант пирамидальной сортировки, который ищет оптимальность (асимптотически оптимальную) относительно нижней границы, полученной с помощью меры предварительной сортировки, используя преимущества существующего порядка в данных. В пирамидальной сортировке для данных $X=\langle x_{1},x_{2},x_{3},\dots ,x_{n}\rangle$ , мы помещаем все n элементов в кучу, а затем продолжаем извлекать максимум (или минимум) n раз. Поскольку время каждого действия максимального извлечения является логарифмическим размером кучи, общее время выполнения стандартной сортировки кучи равно $\color {Blue}O(n\log n)$ . ^[2] При адаптивной сортировке кучи вместо помещения всех элементов в кучу в кучу будут помещаться только возможные максимумы данных (максимальные кандидаты), так что при каждой попытке найти максимум (или минимум).

Сначала декартово дерево. на основе входных данных строится $O(n)$ время, помещая данные в двоичное дерево и делая каждый узел в дереве больше (или меньше), чем все его дочерние узлы, а корень декартова дерева вставляется в пустую двоичную кучу. Затем повторно извлеките максимум из двоичной кучи, извлеките максимум из декартова дерева и добавьте в двоичную кучу его левых и правых дочерних элементов (если они есть), которые сами являются декартовыми деревьями. Если входные данные уже почти отсортированы, декартовы деревья будут очень несбалансированными, с небольшим количеством узлов, имеющими левых и правых дочерних элементов, в результате чего двоичная куча останется небольшой и позволит алгоритму сортировать быстрее, чем $O(n\log n)$ для входных данных, которые уже почти отсортированы. ^[5]

Ниже приведена реализация в псевдокоде: ^[1]

Input: an array of n elements that need to be sortedConstruct the Cartesian tree l(x)Insert the root of l(x) into a heapfor i = from 1 to n{    Perform ExtractMax on the heap     if the max element extracted has any children in l(x)    {        retrieve the children in l(x)        insert the children element into the heap    }}

Недостатки

Несмотря на десятилетия исследований, между теорией адаптивной пирамидальной сортировки и ее практическим применением все еще существует разрыв. Поскольку алгоритм использует декартовы деревья и манипулирование указателями, он имеет низкую эффективность кэш-памяти и высокие требования к памяти, что ухудшает производительность реализаций. ^[4]

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д Левкопулос, К.; Петерссон, О. (1 мая 1993 г.). «Адаптивная пирамидальная сортировка». Журнал алгоритмов . 14 (3): 395–413. дои : 10.1006/jagm.1993.1021 . ISSN 0196-6774 .
^ Jump up to: ^а ^б Шаффер, Р.; Седжвик, Р. (1 июля 1993 г.). «Анализ пирамидальной сортировки». Журнал алгоритмов . 15 (1): 76–100. дои : 10.1006/jagm.1993.1031 . ISSN 0196-6774 .
^ Маннила, Хейкки (апрель 1985 г.). «Меры предварительной сортировки и оптимальные алгоритмы сортировки». Транзакции IEEE на компьютерах . С-34 (4): 318–325. дои : 10.1109/TC.1985.5009382 . ISSN 0018-9340 .
^ Jump up to: ^а ^б ^с Эделькамп, Стефан; Эльмасри, Амр; Катаджайнен, Юрки (2011). «Две оптимальные с постоянным коэффициентом реализации адаптивной пирамидальной сортировки». В Илиопулосе, Костас С.; Смит, Уильям Ф. (ред.). Комбинаторные алгоритмы . Конспекты лекций по информатике. Том. 7056. Шпрингер Берлин Гейдельберг. стр. 195–208. дои : 10.1007/978-3-642-25011-8_16 . ISBN 9783642250118 . S2CID 10325857 .
^ «Архив интересного кода» . www.keithschwarz.com . Проверено 31 октября 2019 г.

[:0-1] Jump up to: ^а ^б ^с ^д Левкопулос, К.; Петерссон, О. (1 мая 1993 г.). «Адаптивная пирамидальная сортировка». Журнал алгоритмов . 14 (3): 395–413. дои : 10.1006/jagm.1993.1021 . ISSN 0196-6774 .

[:1-2] Jump up to: ^а ^б Шаффер, Р.; Седжвик, Р. (1 июля 1993 г.). «Анализ пирамидальной сортировки». Журнал алгоритмов . 15 (1): 76–100. дои : 10.1006/jagm.1993.1031 . ISSN 0196-6774 .

[3] Маннила, Хейкки (апрель 1985 г.). «Меры предварительной сортировки и оптимальные алгоритмы сортировки». Транзакции IEEE на компьютерах . С-34 (4): 318–325. дои : 10.1109/TC.1985.5009382 . ISSN 0018-9340 .

[:2-4] Jump up to: ^а ^б ^с Эделькамп, Стефан; Эльмасри, Амр; Катаджайнен, Юрки (2011). «Две оптимальные с постоянным коэффициентом реализации адаптивной пирамидальной сортировки». В Илиопулосе, Костас С.; Смит, Уильям Ф. (ред.). Комбинаторные алгоритмы . Конспекты лекций по информатике. Том. 7056. Шпрингер Берлин Гейдельберг. стр. 195–208. дои : 10.1007/978-3-642-25011-8_16 . ISBN 9783642250118 . S2CID 10325857 .

[5] «Архив интересного кода» . www.keithschwarz.com . Проверено 31 октября 2019 г.

[1]

[2]

[3]

[4]

[5]