Computer Science: 5th sem ADA Lab Program 2

Analysis and Design of Algorithms Lab.

Question 2

//Sort a given set of elements using Heapsort method and determine the time required to sort the elements.

#include <iostream>

#include <conio.h>

#include <time.h>

using namespace std;

void heapify(int *arr,int n)

//arr= is the array to heapify

//n= number of elements in the array.

{

for(int i=n/2;i>=1;i--)

{

bool heap=false;//assume its not a heap at first

int low=i;

int tmp=arr[low];

while(!heap && 2*low<=n)

{

int j=2*low;

if(j<n)

{

if(arr[j]<arr[j+1])

j++;

}

if(tmp>=arr[j])//compare with original low value

heap=true;

else

{

arr[low]=arr[j];

low=j;

}

}

arr[low]=tmp;

}

}

void heapSort(int *arr,int n)

//array to sort and number of elements

{

for(int i=1;i<=n;i++)

heapify(arr+i-1,n-i+1);

cout<<"Sorted array:\n\n";

for(int i=1;i<=n;i++)

cout<<arr[i]<<"\t";

cout<<"\n";

}

void main()

{

int n;

cout<<"Enter the size of the array:";cin>>n;

cout<<"Enter the array:\n\n";

int *arr=new int[n+1];

for(int i=1;i<=n;i++)

cin>>arr[i];



cout<<"\nHeap Sorting...\n\n";

int start=clock();

heapSort(arr,n);

int time1=(clock()-start)/CLK_TCK;

cout<<"\nTime taken:"<<time1;

getch();

}