heapsorter.cpp

#include "headlines.h"

void HeapSorter::CreateHeap(unsigned k, unsigned n, Stats ** heapStats)
{//Закрытый метод класса "Сортировщик кучей", который осуществляет построение пирамиды.
    long newElement = tempArray[k];
    unsigned child = 0;
    while(k <= n / 2)
    {
        child = 2 * k;
        (*heapStats)->compareCount++;
        if (child < n && this->tempArray[child] < this->tempArray[child + 1])
            child++;
        (*heapStats)->compareCount++;
        if (newElement >= this->tempArray[child]) break;
            this->tempArray[k] = this->tempArray[child];
        k = child;
    }
    this->tempArray[k] = newElement;
}

Stats HeapSorter::SortArray(long * arrayToSort, unsigned length)
{//Сортировка пирамидальная.
    Stats * heapStats = new Stats("Куча");
    this->SetTempArray(arrayToSort, length); //Создаем временный массив.
    long temp = 0;
    for(int i = length / 2 - 1; i >= 0; i--)
        CreateHeap(i, length - 1, &heapStats); //Строим пирамиду.
    for(int i = length - 1; i > 0; i--)
    {
        swap(this->tempArray[i], this->tempArray[0]);
        heapStats->swapCount++;
        CreateHeap(0, i - 1, &heapStats); //Восстанавливаем пирамидальность
    }
    ShowArray(this->tempArray, length);
    return *heapStats;
}