heap

#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

}

******************************************************************

quicksort.h

using namespace std;

//Function to swap two integers void swap(int &a,int &b) { int t=a; a=b; b=t; return; }

int partition(int array[], int left, int right) { int pivot_index=left+rand()%(right-left+1); //Choosing the pivot index randomly int pivot_val=array[pivot_index]; //pivot value for easy reference swap(array[pivot_index],array[right]); //move pivot to the end pivot_index=left; //start looking for correct location for(int i=left; i

void quicksort(int array[], int left, int right) { if(left

void quicksort(int array[],int size) { quicksort(array,0,size-1); return ; }

main()

#include #include #include "quicksort.h"

using namespace std;

int main() { int *arr,n; srand(time(0)); cout>n; while(n>0) { arr=new int[n]; cout>arr[i]; quicksort(arr,n); cout>n; } return 0; }

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

<>

<>

<>

<>

<>

<>

<>

<>

<><>