Simple Heap Sort Program in C

About this program

This is an example program in c sorting programs. Read the concept first: C Array, then study the code and output below.

Definition

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.

Simple Heap Sort Program example

/* Simple Heap Sort Program Using Functions and Array in C*/
/* Data Structure Programs,C Functions and Array Examples */

#include<stdio.h>
#include<conio.h>

#define MAX_SIZE 5

void heap_sort();

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

int main() {
  int i;

  printf("Simple Heap Sort Example - Functions and Array\n");
  printf("\nEnter %d Elements for Sorting\n", MAX_SIZE);
  for (i = 0; i < MAX_SIZE; i++)
    scanf("%d", &arr_sort[i]);

  printf("\nYour Data   :");
  for (i = 0; i < MAX_SIZE; i++) {
    printf("\t%d", arr_sort[i]);
  }

  heap_sort();

  printf("\n\nSorted Data :");
  for (i = 0; i < MAX_SIZE; i++) {
    printf("\t%d", arr_sort[i]);
  }

  getch();

}

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

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

    printf("\nHeap Sort Iteration %d : ", i);
    for (a = 0; a < MAX_SIZE; a++) {
      printf("\t%d", 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);
  }
}

Sample Output

Simple Heap Sort Example - Functions and Array

Enter 5 Elements for Sorting
500
401
300
20
10

Your Data   :   500     401     300     20      10
Heap Sort Iteration 4 :         401     20      300     10      500
Heap Sort Iteration 3 :         300     20      10      401     500
Heap Sort Iteration 2 :         20      10      300     401     500
Heap Sort Iteration 1 :         10      20      300     401     500
Heap Sort Iteration 0 :         10      20      300     401     500

Sorted Data :   10      20      300     401     500

Related Pages

Learn the concept first, then study the code:

• Data Structures — Browse all Data Structures.
• C Array — Concept — sorting operates on array elements.
• Simple Bubble Sort Program in C — More in c sorting programs.
• Simple Bubble Sort Program using functions in C — More in c sorting programs.