Записки программиста Программирование и не только

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

Сортировка:
1. Быстрая сортировка (англ. quicksort)
2. Сортировка Шелла (англ. Shell sort)

Поиск:
1. Прямой поиск (он же Простой, он же Алгоритм грубой силы)
2. Алгоритм Бойера-Мура-Хорспула

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

Данный вид сортировки основан на логическом представлении исходного массива в виде паримиды. Номер элемента в пирамиде вычисляется как 2n+1 и 2n+2 для потомков (n – номер родителя) и (n-1)/2 для родителя (n – номер потомка). Нумерация в пирамиде ведется с нуля.

Алгоритм:

1. Построение пирамиды – проверка условия пирамидальности - каждый родитель должен быть больше своего потомка.

2. Сортировка пирамиды.

а) Поменять местами значения первого и последнего узлов пирамиды;

б) Отделить последний узел от дерева, уменьшив размер дерева на единицу (элемент остаётся в массиве);

в) Восстановить пирамиду, просеяв вниз её новый корневой элемент;

г) Перейти к пункту (а);

Боевой пример:

void DownHeap(int Arr[], int index, int Count, int Current)
{
	//Функция пробегает по пирамиде восстанавливая ее
	//Также используется для изначального создания пирамиды
	//Использование: Передать номер следующего элемента в index
	//Процедура пробежит по всем потомкам и найдет нужное место для следующего элемента
	int Child;
	while (index < (Count/2))
	{
		Child = (index+1)*2-1;
		if ((Child < Count-1) && (Arr[Child] < Arr[Child+1])) Child++;
		if (Current >= Arr[Child]) break;
		Arr[index] = Arr[Child];
		index = Child;
	}
	Arr[index] = Current;
}

void heapSort(int Arr[], int Count)
{
//Основная функция
	int i;
	int Current;
	//Собираем пирамиду
	for (i = (Count/2)-1; i >= 0; i--) DownHeap(Arr, i, Count, Arr[i]);
	//Пирамида собрана. Теперь сортируем
	for (i = Count-1; i > 0; i--)
	{
		Current = Arr[i]; //перемещаем верхушку в начало отсортированного списка
		Arr[i] = Arr[0];
		DownHeap(Arr, 0, i, Current); //находим нужное место в пирамиде для нового элемента
	}
}

Код переписан и отлажен совместно с Di
Спасибо за указание на ошибку Barin