Ternary Heap Sort Algorithm Implementation Using heap Data Structure

Ternary Heap Sort Algorithm Implementation Using heap Data Structure :


Ternary Heap Sort Algorithm Code:

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>

#define SIZE 10000
long A[SIZE], heapsize = SIZE;

void maxHeapify(long i){
    long largest;

    /**
     * Find index of first, second, third child
     */
    long l = 3 * i + 1;
    long m = 3 * i + 2;
    long r = 3 * i + 3;

    /**
     * Find largest among the parent and its child. And save that index
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    if(m < heapsize && A[m] > A[largest])
        largest = m;

    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /**
     * If the largest index is not of parent then there is another bigger value
     * So swap that value with parent
     */
    if(largest != i){
        std::swap(A[i], A[largest]);
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    long j;
    /**
     * Starting from the last parent to root max heapify
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    long i;
    /**
     * Send biggest value root in the end
     * then max heapify from root again
     * this procedure sorts in ascending order because of max heap
     */
    for(i = heapsize-1; i > 0; --i){
        std::swap(A[0], A[i]);

        --heapsize;
        maxHeapify(0);
    }
}

int main(){
    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    register long i = 0;
    for(; i < SIZE; ++i){
        A[i] = rand() % SIZE;
        //printf("%ld ", A[i]);
    }
    //printf("\n");

    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    for(i = 0; i < SIZE; ++i)
        printf("%ld ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s