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

 изобретенный Д. Уилльямсом, является улучшением традиционных сортировок с помощью дерева.

Пирамидой (кучей) называется двоичное дерево такое, что

a[i] ≤ a[2i+1];

a[i] ≤ a[2i+2].

 

 

a[0] — минимальный элемент пирамиды.

Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов.

1) static Int32 add2pyramid(Int32[] arr, Int32 i, Int32 N)

{

Int32 imax;

Int32 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;

}

 

static void Pyramid_Sort(Int32[] arr, Int32 len)

{

//step 1: building the pyramid

for (Int32 i = len / 2 - 1; i >= 0; --i)

{

long prev_i = i;

i = add2pyramid(arr, i, len);

if (prev_i!= i) ++i;

}

 

//step 2: sorting

Int32 buf;

for (Int32 k = len - 1; k > 0; --k)

{

buf = arr[0];

arr[0] = arr[k];

arr[k] = buf;

Int32 i = 0, prev_i = -1;

while (i!= prev_i)

{

prev_i = i;

i = add2pyramid(arr, i, k);

}

}

}

 

static void Main(string[] args)

{

Int32[] arr = new Int32[100];

//заполняем массив случайными числами

Random rd = new Random();

for(Int32 i = 0; i < arr.Length; ++i) {

arr[i] = rd.Next(1, 101);

}

System.Console.WriteLine("The array before sorting:");

foreach (Int32 x in arr)

{

System.Console.Write(x + " ");

}

//сортировка

Pyramid_Sort(arr, arr.Length);

 

System.Console.WriteLine("\n\nThe array after sorting:");

foreach (Int32 x in arr)

{

System.Console.Write(x + " ");

}

System.Console.WriteLine("\n\nPress the <Enter> key");

System.Console.ReadLine();

}

 2) public class Heap<T>

{

private T[] _array; //массив сортируемых элементов

private int heapsize;//число необработанных элементов

private IComparer<T> _comparer;

public Heap(T[] a, IComparer<T> comparer){

_array = a;

heapsize = a.Length;

_comparer = comparer;

}

 

public void HeapSort(){

build_max_heap();//Построение пирамиды

for(int i = _array.Length - 1; i > 0; i--){

 

T temp = _array[0];//Переместим текущий максимальный элемент из нулевой позиции в хвост массива

_array[0] = _array[i];

_array[i] = temp;

 

heapsize--;//Уменьшим число необработанных элементов

max_heapify(0);//Восстановление свойства пирамиды

}

}

 

private int parent (int i) { return (i-1)/2; }//Индекс родительского узла

private int left (int i) { return 2*i+1; }//Индекс левого потомка

private int right (int i) { return 2*i+2; }//Индекс правого потомка

 

//Метод переупорядочивает элементы пирамиды при условии,

//что элемент с индексом i меньше хотя бы одного из своих потомков, нарушая тем самым свойство невозрастающей пирамиды

private void max_heapify(int i){

int l = left(i);

int r = right(i);

int lagest = i;

if (l<heapsize && _comparer.Compare(_array[l], _array[i])>0)

lagest = l;

if (r<heapsize && _comparer.Compare(_array[r], _array[lagest])>0)

lagest = r;

if (lagest!= i)

{

T temp = _array[i];

_array[i] = _array[lagest];

_array[lagest] = temp;

 

max_heapify(lagest);

}

}

 

//метод строит невозрастающую пирамиду

private void build_max_heap(){

int i = (_array.Length-1)/2;

 

while(i>=0){

max_heapify(i);

i--;

}

}

 

}

 

public class IntComparer: IComparer<int>

{

public int Compare(int x, int y) {return x-y;}

}

 

public static void Main (string[] args)

{

int[] arr = Console.ReadLine().Split(' ').Select(s=>int.Parse(s)).ToArray();//вводим элементы массива через пробел

IntComparer myComparer = new IntComparer();//Класс, реализующий сравнение

Heap<int> heap = new Heap<int>(arr, myComparer);

heap.HeapSort();

}

Алгоритм плавной сортировки (Smooth Sort).

Был изобретен Э. В. Дейкстрой в 1981 году и является развитием идеи Heap Sort (пирамидальной сортировки).

Реализован на языке программирования C#. Консольное приложение.

Пример кода из программы приведен ниже.