c++

C++ Program to Implement Heap Sort Algorithm Full Project For Beginners


 

Welcome folks today in this blog post we will be implementing heap sort algorithm in c++ All the full source code of the application is shown below.

 

 

 

 

 

 

In order to get started you need to make a app.cpp file and copy paste the following code

 

 

app.cpp

 

 

#include <stdio.h>
#define size 4//pre-defining the array length to be 4
void swap(int* p, int* q)//this function swaps the values to which pointers p and q point
{
    int temporary = *q;
    *q = *p;
    *p = temporary;
}
void inputArray(int array[],int length)
 {
     printf("Input %d (integer) elements: ",length);
     //note, in the for loop, the intitializing statement is decreasing the value of length by 1 because in arrays, counting starts from 0
     for(length--;length>=0;length--){
        scanf("%d",&array[length]);
     }
 }
void printArray(int array[],int length)
 {
     printf("The elements of the given array are: ");
     for(int i=0;i<length;i++)printf("%d ",array[i]);
 }
void heapify(int array[], int length, int index) 
{ 
    int largest = index; // taking value of 'index' as root-index 
    int left = 2*index + 1;//left node of the virtual binary tree
    int right = 2*index + 2;//right node of the virtual binary tree
    if (left < length && array[left] > array[largest]) largest = left;//taking 'left' as root-index if 'array[left]' is greater 
    if (right < length && array[right] > array[largest]) largest = right;//taking 'right' as root-index if 'array[right]' is greater
    if (largest != index)//if the original root-index in the function is changed 
    { 
        swap(&array[index], &array[largest]);//swapping the value at original root-index  with that at changed root-index
        heapify(array, length, largest);//using recursion to heapify further with the changed root-index
    } 
}
void heapSort(int array[], int length) 
{ 
    int i;
    for (i = length / 2 - 1; i >= 0; i--) heapify(array, length, i); //building the heap in array
    for (i=length-1; i>=0; i--)//extracting elements from heap
    { 
        swap(&array[0], &array[i]);//swapping value at current-root with the value at end
        heapify(array, i, 0);//heapifying
    } 
} 
int main()
{
    int array[size];
    inputArray(array,size);
    heapSort(array,size);
    printArray(array,size);
    return 0;
}

 

Similar Posts:

    None Found

Leave a Reply

Your email address will not be published. Required fields are marked *