Heap Sort Program - C/C++

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(nlog n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

The heapsort algorithm can be divided into two parts.
1. In the first step, a heap is built out of the data.
2. In the second step, a sorted array is created by repeatedly removing the largest element from the heap, and inserting it into the array. The heap is reconstructed after each removal. Once all objects have been removed from the heap, we have a sorted array. The direction of the sorted elements can be varied by choosing a min-heap or max-heap in step one.

Below is the implementation of heap sort in C++.


#include<stdio.h>
void makeheap(int a[], int n)
{
 int i, temp, k, j;
 for (i = 1; i<n; i++)
 
 {
  temp = a[i];
  k = (i - 1) / 2;
  j = i;
  while (j>0 && a[k] < temp)
  {
   a[j] = a[k];
   j = k;
   k = (j - 1) / 2;
  }
  a[j] = temp;
 }
}
void disp(int a[], int n)
{
 int i;
 for (i = 0; i < n; i++)
 {
  printf("%d,"a[i]);
 }
 printf("\b");
 printf(" ");
}
void sortheap(int a[], int n)
{
 int temp, i, j;
 for (i = n - 1; i >= 1; i--)
 {
  temp = a[i];
  a[i] = a[0];
  a[0] = temp;
  makeheap(a, i);
  printf("\n\t-->");
  disp(an);
 }
}
void main()
 
{
 int a[100], n, i;
 clrscr();
 printf("\n\tEnter Size := ");
 scanf("%d", &n);
 clrscr();
 printf("\n\tEnter Array Elements \n");
 for (i = 0; i < n; i++)
 {
  printf("\tElement %d := ", i + 1);
  scanf("%d", &a[i]);
 }
 makeheap(a, n);
 printf("\n\tHeap Created := ");
 disp(a, n);
 sortheap(a, n);
 printf("\n\n\tSorted Elements := ");
 disp(a, n);
 getch();
}

Check out other methods of sorting in Data Structure :
1. Implementation of Insertion Sort in C
2. Implementation of Selection Sort in C
3. Implementation of Quick Sort in C
4. Implementation of Bubble Sort in C
5. Implementation of Heap sort in C
6. Implementation of Merge Sort in C
7. Implementation of Radix Sort in C

1 comments :

Post a Comment