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();
}
No comments:
Post a Comment