Compare performance of heap sort and merge sort for sorting an input array of le

Question

Compare performance of heap sort and merge sort for sorting an input array of length n. Each element in the array input is a random number in the range 1 to n. Conduct the timing experiment for n=1k,2k,4k,...,128k

Explanation / Answer

#include #include #include #define Parent(i) i/2 #define Left(i) 2*i #define Right(i) 2*i+1 int swap( int* a, int* b) { int tmp; tmp=*a; *a= *b; *b=tmp; } void Max_Heapify(int a[], int hsize, int i) { int l, r, largest; l=Left(i); r=Right(i); if ((l a[i])) largest = l; else largest = i; if ((r a[largest])) largest = r; if(largest != i) { swap(&a[i], &a[largest]); Max_Heapify(a, hsize, largest); } } /******************************/ void Build_Max_Heap(int a[], int hsize) { int i; for(i=hsize/2; i>=1; i--) Max_Heapify(a, hsize, i); } void heapsort(int *a, int hsize) { int i; Build_Max_Heap(a, hsize); for(i=hsize; i>=2; i--) { swap( &a[1], &a[i]); hsize--; Max_Heapify(a, hsize, 1); } } void merge(int *a,int l,int m,int h) { int length= h-l+1; int temp[length]; int i; int l_clone=l; int m_clone=m; int h_clone=h; for(i = 0; i

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.