heap sort
#include
using namespace std;
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void Heapify(int maxheap[],int root,int n)
{
int max=root;
int left=2*root+1;
int right=2*root+2;
if(root>=0 && left=0 && right if(max!=root)
{
swap(&maxheap[root],&maxheap[max]);
Heapify(maxheap,(root-2)/2,n);
}
}
void topDownHeapify(int a[],int n)
{
int maxheap[n];
for(int i=0;i {
maxheap[i]=a[i];
Heapify(maxheap,(i-2)/2,i+1);
}
for(int i=0;i cout
}
void bottomUpHeapify(int a[],int root,int n)
{
int max=root;
int left=2*root+1;
int right=2*root+2;
if(left if(right if(max!=root)
{
swap(&a[root],&a[max]);
Heapify(a,max,n);
}
}
void sort(int a[],int n)
{
for(int i=n-1;i>=0 ;i--)
{
swap(&a[0],&a[i]);
bottomUpHeapify(a,0,i);
}
}
int main()
{
int n,i,j;
cout
cin>>n;
int *arr=new int[n];
for(i=0;i {
cout
cin>>arr[i];
}
cout
for(i=0;i cout
cout
topDownHeapify(arr,n);
cout
for(i=(n/2-1); i>=0; i--)
bottomUpHeapify(arr,i,n);
for(i=0;i cout
cout
sort(arr,n);
for(i=0;i cout
}
Assignment: Template Functions for Sorting and Timing Performance Generalizing the Sorting and Heap Functions Begin by modifying the sorting and heap functions you created in lab so that they use template types, and can be used with arrays of any type of data that is capable of being compared with the library: you have at least used it to get the current system time for seeding a random number generator. The time() function returns a value that is (generally) expressed in seconds. This is far to imprecise a value for timing most algorithms on modern computing equipment. Fortunately the C++11 standard adds a new, standard option in the cchrono> library 1 2. The cchrono> library defines three kinds of clock: system_clock for measuring time in relation to a real-time clock (or "wall clock") steady_clock for measuring elapsed time (not necessary related to real-time) high resolution_clock for measuring time with the shortest available time point period (which may or may not be the same thing as either the system clock or the steady_clock) For our purposes the high resolution_clock will be of the most use. All three types of clock are capable of producing the current time point by calling their now() method. The now () method will return a time_point of the appropriate type for the clock being queried. For the high_resolution_clock, the type name for the time point is std::chrono::high_resolution_clock: :time_point. Once we have a time point for the starting and ending time of the process we want to profile, we can simply subtract them to produce an elapsed time (the time it took to complete the process). This elapsed time can be stored in an object of type std::chrono: : duration double>. The duration object can then produce a (double-precision) representation of the number of seconds that elapsed by calling its count() method. Assignment: Template Functions for Sorting and Timing Performance Generalizing the Sorting and Heap Functions Begin by modifying the sorting and heap functions you created in lab so that they use template types, and can be used with arrays of any type of data that is capable of being compared with the library: you have at least used it to get the current system time for seeding a random number generator. The time() function returns a value that is (generally) expressed in seconds. This is far to imprecise a value for timing most algorithms on modern computing equipment. Fortunately the C++11 standard adds a new, standard option in the cchrono> library 1 2. The cchrono> library defines three kinds of clock: system_clock for measuring time in relation to a real-time clock (or "wall clock") steady_clock for measuring elapsed time (not necessary related to real-time) high resolution_clock for measuring time with the shortest available time point period (which may or may not be the same thing as either the system clock or the steady_clock) For our purposes the high resolution_clock will be of the most use. All three types of clock are capable of producing the current time point by calling their now() method. The now () method will return a time_point of the appropriate type for the clock being queried. For the high_resolution_clock, the type name for the time point is std::chrono::high_resolution_clock: :time_point. Once we have a time point for the starting and ending time of the process we want to profile, we can simply subtract them to produce an elapsed time (the time it took to complete the process). This elapsed time can be stored in an object of type std::chrono: : duration double>. The duration object can then produce a (double-precision) representation of the number of seconds that elapsed by calling its count() method<>
<>
<>
<>
<>
<>
<>
<>
<><>
