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


На главную
Содержание


Пошаговое описание алгоритма

1. Построение пирамиды
Пирамида представляет собой дерево, в котором каждый узел имеет не более двух потомков, причем узел всегда больше или равен своим потомкам (таким образом, на вершине дерева всегда находится наибольший элемент).

Если в исходном массиве n элементов, то последние (n / 2) элемента становятся основанием пирамиды (эти элементы являются листьями дерева, т.е. у них нет потомков, поэтому для них вышеуказанное правило выполняется автоматически).

Удобнее всего поместить пирамиду в массив. При этом распределение индексов массива по узлам дерева будет выглядеть так (на этом рисунке все цифры - это индексы элементов массива, а ни в коем случае не значения этих элементов):
Индексирование узлов дерева

Таким образом, для того, чтобы каждый узел дерева был больше своих потомков, каждый элемент массива a[i] должен быть больше или равен элементам a[2 * i + 1] и a[2 * i + 2].

2. Сортировка
В этой части алгоритма мы перемещаем в конец массива максимальный элемент, затем исключаем его из дальнейшего процесса сортировки. Поскольку максимальный элемент всегда находится на вершине пирамиды, мы должны поменять местами элементы a[0] и a[n-1] (т.е. последний элемент). Причем элемент a[n-1] необходимо добавлять так, чтобы не нарушился порядок пирамиды (при этом пирамиду придется частично перестроить). Далее мы будем рассматривать массив только до (n-2)-го элемента.
На следующем шаге мы меняем местами a[0] и a[n-2] и далее рассматриваем массив только до (n-3)-го элемента. Повторяем всю эту процедуру до тех пор, пока в рассматриваемой части массива не останется один элемент.


Реализация на C#

Класс PyramidSorting, содержащий функцию пирамидальной сортировки, и класс Test для тестирования этой функции:

class PyramidSorting {
//add 1 element to the pyramid
static int add2pyramid(double[] arr, int i, int N) {
int imax;
double buf;
if((2*i+2) < N) {
if(arr[2*i+1] < arr[2*i+2]) imax = 2 * i + 2;
else imax = 2 * i + 1;
}
else imax = 2 * i + 1;
if(imax >= N) return i;
if(arr[i] < arr[imax]) {
buf = arr[i];
arr[i] = arr[imax];
arr[imax] = buf;
if(imax < N/2)i = imax;
}
return i;
}
public static void sorting(double[] arr, int len) {
//step 1: building the pyramid
for(int i = len/2 - 1; i >= 0; --i) {
long prev_i = i;
i = add2pyramid(arr, i, len);
if(prev_i != i) ++i;
}

//step 2: sorting
double buf;
for(int k = len-1; k > 0; --k) {
buf = arr[0];
arr[0] = arr[k];
arr[k] = buf;
int i = 0, prev_i = -1;
while(i != prev_i) {
prev_i = i;
i = add2pyramid(arr, i, k);
}
}
}
}
class Test {
static void Main(string[] args) {
double[] arr = new double[100];

//fill the array with random numbers
Random rd = new Random();
for(int i = 0; i < arr.Length; ++i) {
arr[i] = rd.Next(1, 101);
}
System.Console.WriteLine("The array before sorting:");
foreach(double x in arr) {
System.Console.Write(x + " ");
}
PyramidSorting.sorting(arr, arr.Length);
System.Console.WriteLine("\n\nThe array after sorting:");
foreach(double x in arr) {
System.Console.Write(x + " ");
}
System.Console.WriteLine("\n\nPress the <Enter> key");
System.Console.ReadLine();
}
}
Функция add2pyramid() добавляет один элемент к пирамиде, перестраивая ее таким образом, чтобы не нарушалось правило, согласно которому узел не может быть меньше своих потомков.
Функция sorting() отвечает непосредственно за сортировку.

На главную

Автотехника Сантехника Флора Косметика Одежда Часы

Fatal error: Call to a member function return_links() on a non-object in /home/h17u52/public_html/trubetskoy1.ru/_count.inc on line 21