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

10Окт/092

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

Сортировка:
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

Комментарии (2) Пинги (0)
  1. ошибка в условии: for (i = (Count/2)-1; i > 0; i—) DownHeap(Arr, i, Count, Arr[i]);

    ошибка в условии: for (i = Count-1; i > 0; i—)

    правильно: i >= 0 (в C++ массивы начинаются с индекса 0, при строгом неравенстве мы пропустим элемент с этим индексом)

    • Да, проверил, про первое условие — правда. Статью исправил
      Src: 2 5 6 1 0 7 9 22 0 54
      Sort: 0 0 1 5 6 7 9 22 54 2

      А вот про второе услови — не уверен, не влияет оно на результат сортировки, т.к. в самом цикле мы уже работаем с индексом 0.

      Есть тестовые данные, на которых второе условие неправильно работает?


Leave a comment

Trackbacks are disabled.