Ternary Heap Sort Code in C++ using Heap Data structure

Introduction:

This code is implementation of ternary heap sort. The code requires no input. Data inputs (integers) are generated randomly then sorted using heap sort.

Only change the define SIZE value to for sorting large or small amount of numbers.

Code for Binary Heap Sort here.

Ternary Heap Sort Code Cpp:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Ternary Heap Sort
 */

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

#define SIZE 10
int A[SIZE], heapsize = SIZE;

void maxHeapify(int i){
    int largest;

    /**
     * Find right child index
     */
    int l = 3 * i + 1;

    /**
     * Compare left child against the current node
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * find mid child index
     */
    int m = 3 * i + 2;

    /**
     * Compare mid child against the calculated largest value node
     */
    if(m < heapsize && A[m] > A[largest])
        largest = m;

    /**
     * Find right child index
     */
    int r = 3 * i + 3;

    /**
     * Compare right child against the calculated largest value node
     */
    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /*
     * If child nodes have larger value then current node
     */
    if(largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    int j;
    /**
     * operate on third of array
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    int i;
    for(i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);

        /**
         * Decrease the heap size as right of heap is already sorted
         */
        --heapsize;

        /**
         * Again max heapify the rest of the heap
         */
        maxHeapify(0);
    }
}

int main(){
    int i;

    clock_t begin, end;
    double time_elapsed;

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

    printf("Sorting Now....\n");
    begin = clock();
    heapsort();
    end = clock();

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

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

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

    return 0;
}

Binary Heap Sort Algorithm Code Using Heap Data Structure

Binary Heap Sort Algorithm Code Using Heap Data Structure:


Binary Heap Sort Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

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

#define SIZE 10000
long A[SIZE];

/**
 * In the beginning the heap size is same as the array size
 */
long heapsize = SIZE;

void maxHeapify(long i){
    long largest;

    /**
     * Find right child index
     */
    long l = 2 * i + 1;

    /**
     * Compare left child against the current node
     */
    if (l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * Find right child index
     */
    long r = 2 * i +2;

    /**
     * Compare right child against the calculated largest value node
     */
    if (r < heapsize && A[r] > A[largest])
        largest = r;

    /**
     * Swap the current value with the largest value
     */
    if (largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}


void buildMaxHeap(){
    register long j;
    /**
     * Start from the last parent and go to root
     */
    for (j = heapsize / 2 - 1; j >= 0; --j)
        maxHeapify(j);
}


void heapsort(){
    buildMaxHeap();
    /**
     * Start from the end of heap swap with root and decrease heap size
     * We know in max heap the biggest item is on top so swapping with the
     * last element will put the biggest value in the end. That way the
     * smallest value will be at the beginning and the biggest will be at the end
     * So by using max heap we can sort in Ascending order.
     */
    register long i;
    for (i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);
        --heapsize;
        maxHeapify(0);
    }
}

int main(){
    register long i = 0;

    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    for (i = 0; i < SIZE; ++i)
        A[i] = rand() % SIZE;

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

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

    /**
     * Comment this code if you do not want to see sorted output but just time
     */
    for(i = 0; i < SIZE; ++i)
        printf("%ld ", A[i]);

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

    return 0;
}