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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Анимированная схема алгоритма

Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за Θ(n log n) операций при сортировке n элементов.[2] Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)).

Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.

История создания[править | править код]

Пирамидальная сортировка была предложена Дж. Уильямсом[en] в 1964 году.[1]

Алгоритм[править | править код]

Пример сортирующего дерева
структура хранения данных сортирующего дерева

Сортировка пирамидой использует бинарное сортирующее дерево. Сортирующее дерево — это такое дерево, у которого выполнены условия:

  1. Каждый лист имеет глубину либо , либо ,  — максимальная глубина дерева.
  2. Значение в любой вершине не меньше (другой вариант — не больше) значения её потомков.

Удобная структура данных для сортирующего дерева — такой массив Array, что Array[0] — элемент в корне, а потомки элемента Array[i] являются Array[2i+1] и Array[2i+2].

Алгоритм сортировки будет состоять из двух основных шагов:

1. Выстраиваем элементы массива в виде сортирующего дерева[источник не указан 1274 дня]:

при .

Этот шаг требует операций.

2. Будем удалять элементы из корня по одному за раз и перестраивать дерево. То есть на первом шаге обмениваем Array[0] и Array[n-1], преобразовываем Array[0], Array[1], … , Array[n-2] в сортирующее дерево. Затем переставляем Array[0] и Array[n-2], преобразовываем Array[0], Array[1], … , Array[n-3] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[0], Array[1], … , Array[n-1] — упорядоченная последовательность.

Этот шаг требует операций.

 1 #include <iostream>
 2 #include <vector>
 3 #include <ctime>
 4 void swap(std::vector<int> *v, int n, int m)
 5 {
 6 	int tmp = (*v)[n];
 7 	(*v)[n] = (*v)[m];
 8 	(*v)[m] = tmp;
 9 	/*
10 	for (int i = 0; i < (*v).size(); i++)
11 	{
12 		std::cout << (*v)[i] << " ";
13 	}
14 	std::cout << std::endl;
15 	*/
16 }
17 int main()
18 {
19 	std::vector<int> arr;
20 	const int N = 20;
21 	srand(time(0));
22 	for (int i = 0; i < N; i++)
23 	{
24 		arr.push_back((int)rand() % 100);
25 		std::cout << arr[i] << " ";
26 	}
27 	std::cout << std::endl;
28 	for (int j = 0; j < N; j++)
29 	{
30 		for (int i = N / 2 -1 - j/2; i > -1; i--)
31 		{
32 			if (2 * i + 2 <= N - 1-j)
33 			{
34 				if (arr[2 * i + 1] > arr[2 * i + 2])
35 				{
36 					if (arr[i] < arr[2 * i + 1])
37 					{
38 						swap(&arr, i, 2 * i + 1);
39 						//std::cout <<j<<" "<< i << " " << 2 * i + 1 << std::endl;
40 					}
41 				}
42 				else
43 					if (arr[i] < arr[2 * i + 2])
44 					{
45 						swap(&arr, i, 2 * i + 2);
46 						//std::cout <<j<<" "<< i << " " << 2 * i + 2 << std::endl;
47 					}
48 			}
49 			else
50 				if (2 * i + 1 <= N - 1-j)
51 					if (arr[i] < arr[2 * i + 1])
52 						swap(&arr, i, 2 * i + 1);
53 		}
54 		swap(&arr,0, N - 1 - j);
55 		//std::cout << j << " " << 0 << " " << N-1-j << std::endl;
56 	}
57 	for (int i = 0; i < N; i++)
58 	{
59 		std::cout << arr[i] << " ";
60 	}
61 	std::cout << std::endl;
62 }

Достоинства и недостатки[править | править код]

Достоинства

  • Имеет доказанную оценку худшего случая .
  • Сортирует на месте, то есть требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

  • Неустойчив — для обеспечения устойчивости нужно расширять ключ.
  • На почти отсортированных массивах работает столь же долго, как и на хаотических данных.
  • На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.
  • Методу требуется «мгновенный» прямой доступ; не работает на связанных списках и других структурах памяти последовательного доступа.
  • Не распараллеливается.

Сортировка слиянием при расходе памяти O(n) быстрее ( с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

Применение[править | править код]

Алгоритм «сортировка кучей» активно применяется в ядре Linux.

Может быть очень удобным если требуется отсортировать не весь массив, а получить, например, только несколько максимальных элементов. После шага построения сортирующего дерева далее следуют только несколько шагов извлечения максимального элемента из корня кучи, именно так работает std::partial_sort() из стандартной библиотеки C++.

Примечания[править | править код]

Литература[править | править код]

Ссылки[править | править код]