C++ Programming Code Examples

C++ > Sorting Searching Code Examples

Simple Heap Sort Program in C++



Simple Heap Sort Program in C++

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

#include <iostream>
#include<conio.h>
#include<stdlib.h>

#define maxsize 5

using namespace std;

void heap_sort();

void heap_adjust(int, int);
int arr_sort[maxsize], t, a;

int main() {
    int i;

    cout << "Simple C++ Heap Sort Example - Functions and Array\n";
    cout << "\nEnter " << maxsize << " Elements for Sorting : " << endl;
    for (i = 0; i < maxsize; i++)
        cin >> arr_sort[i];

    cout << "\nYour Data   :";
    for (i = 0; i < maxsize; i++) {
        cout << "\t" << arr_sort[i];
    }

    heap_sort();

    cout << "\n\nSorted Data :";
    for (i = 0; i < maxsize; i++) {
        cout << "\t" << arr_sort[i];
    }

    getch();

}

void heap_sort() {
    for (int i = maxsize / 2 - 1; i >= 0; i--)
        heap_adjust(maxsize, i);

    for (int i = maxsize - 1; i >= 0; i--) {
        //Swapping Values 
        t = arr_sort[0];
        arr_sort[0] = arr_sort[i];
        arr_sort[i] = t;
        heap_adjust(i, 0);

        cout << "\nHeap Sort Iteration : " << i;
        for (a = 0; a < maxsize; a++) {
            cout << "\t" << arr_sort[a];
        }
    }
}

void heap_adjust(int n, int i) {
    int large = i, left = 2 * i + 1, right = 2 * i + 2;

    // adjest left child
    if (left < n && arr_sort[left] > arr_sort[large])
        large = left;

    // adjest right child
    if (right < n && arr_sort[right] > arr_sort[large])
        large = right;


    if (large != i) {
        //Swapping Values 
        t = arr_sort[i];
        arr_sort[i] = arr_sort[large];
        arr_sort[large] = t;
        heap_adjust(n, large);
    }
}