Wednesday 12 October 2011

Source code for heap sort


// HeapSort.cpp : Defines the entry point for the console application.
#include <iostream>
#include <conio.h>
#include <malloc.h>

void Heap_Sort(int [], int, int);
void Max_Heapify(int [], int, int);
void Build_Max_Heap(int [], int);

void Heap_Sort(int A[], int length, int heapsize)
{
 Build_Max_Heap(A, length);
 for(int i = length; i >= 2; i--)
 {
  int temp;
  temp = A[1];
  A[1] = A[i];
  A[i] = temp;
  heapsize = heapsize-1;
  Max_Heapify(A, 1, heapsize);
 }
}


void Build_Max_Heap(int A[], int length)
{
 int heapsize;
 heapsize = length;
 for(int i = (length/2); i >= 1; i--)
  Max_Heapify(A, i, heapsize);
}

void Max_Heapify(int A[], int i, int heapsize)
{
 int l, r, largest;
 l = 2*i;
 r = l+1;
 if(l <= heapsize && A[l] > A[i])
  largest = l;
 else
  largest = i;
 if(r <= heapsize && A[r] > A[largest])
  largest = r;
 if(largest != i)
 {
  int temp;
  temp = A[i];
  A[i] = A[largest];
  A[largest] = temp;
  Max_Heapify(A, largest, heapsize);
 }

}
int main()
{
 int length,heapsize;
 int A[10];
 cout << "Enter the no of elements: ";
 cin >> length;
 heapsize =length;
 //A = (int*) malloc(sizeof(int)*length);
 cout << "\nEnter the elements :\n\n";
 for(int i=1; i <= length; i++)
  cin >> A[i];
 Heap_Sort(A, length, heapsize);
 cout << "\nSorted array is : ";
 for(int i = 1; i <= length; i++)
  cout << A[i] << " ";
 getch();
 return 0;
}

No comments:

Post a Comment