Using the C programming language implement Heapsort in the manner described in class. Remember, you need only implement the sort algorithm, both the comparison and main functions have been provided. Please also state how to implement the algorithm into the given code and how to run it.

Here is an example code to use as a guideline

/* * * after splitting this file into the five source files: * * srt.h, main.c, srtbubb.c, srtinsr.c, srtmerg.c * * compile using the command: * * gcc -std=c99 -DRAND -DPRNT -DTYPE=(float | double) -D(BUBB | HEAP | INSR | MERG) *.c * */ /* * * srt.h file * */ #ifndef SRT_H #define SRT_H #include  #define MAX_BUF 256 #define swap(qx,qy,sz) \ do { \ char buf[MAX_BUF]; \ char *q1 = qx; \ char *q2 = qy; \ for (size_t m, ms = sz; ms > 0; ms -= m, q1 += m, q2 += m) { \ m = ms < sizeof(buf) ? ms : sizeof(buf); \ memcpy(buf, q1, m); \ memcpy(q1, q2, m); \ memcpy(q2, buf, m); \ } \ } while (0) void srtbubb(void *, size_t, size_t, int (*)(const void *, const void *)); void srtheap(void *, size_t, size_t, int (*)(const void *, const void *)); void srtinsr(void *, size_t, size_t, int (*)(const void *, const void *)); void srtmerg(void *, size_t, size_t, int (*)(const void *, const void *)); #endif /* SRT_H */ /* * * main.c file * */ #include  #include  #include  #include "srt.h" static int compare(const void *, const void *); int main(int argc, char *argv[]) { int nelem = argc == 2 ? atoi(argv[1]) : SHRT_MAX; TYPE *a = calloc(nelem, sizeof(TYPE)); #ifdef RAND for (int i = 0; i < nelem; ++i) { a[i] = (TYPE)rand() / RAND_MAX; } #else for (int i = 0; i < nelem; ++i) { a[i] = i; } #endif #if defined BUBB srtbubb(a, nelem, sizeof(TYPE), compare); #elif defined HEAP srtheap(a, nelem, sizeof(TYPE), compare); #elif defined INSR srtinsr(a, nelem, sizeof(TYPE), compare); #elif defined MERG srtmerg(a, nelem, sizeof(TYPE), compare); #else qsort(a, nelem, sizeof(TYPE), compare); #endif #ifdef PRNT for (int i = 0; i < nelem; ++i) { printf("%f ", a[i]); } #else for (int i = 0; i < nelem - 1; ++i) { if (a[i] > a[i + 1]) { printf("fail "); goto end; } } printf("pass "); #endif end: free(a); return 0; } static int compare(const void *p1, const void *p2) { if (*(TYPE *)p1 < *(TYPE *)p2) { return -5; } else if (*(TYPE *)p1 > *(TYPE *)p2) { return +5; } return 0; } /* * * srtbubb.c file * */ #include  #include  #include "srt.h" void srtbubb(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) { for (size_t i = nelem - 1; i > 0; --i) { bool sorted = true; for (size_t j = 0; j < i; ++j) { char *qj = (char *)base + size * j; char *qn = qj + size; if (compar(qj, qn) > 0) { swap(qj, qn, size); sorted = false; } } if (sorted) { break; } } return; } /* * * srtinsr.c file * */ #include  #include  #include "srt.h" void srtinsr(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) { char buf[size], *qb = base; for (size_t i = 1; i < nelem; ++i) { memcpy(buf, qb + size * i, size); size_t j = i; while (j > 0 && compar(buf, qb + size * (j - 1)) < 0) { memcpy(qb + size * j, qb + size * (j - 1), size); --j; } memcpy(qb + size * j, buf, size); } return; } /* * * srtmerg.c file * */ #include  #include  #include "srt.h" void srtmerg(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) { char *qb = base, *ql, *qr, *qt; size_t i, j, l, r; if (nelem <= 1) { return; } else if (nelem == 2) { if (compar(qb, qb + size) > 0) { swap(qb, qb + size, size); } return; } l = nelem / 2; r = nelem - l; ql = qt = malloc(size * l); memcpy(ql, qb, size * l); qr = qb + size * l; srtmerg(ql, l, size, compar); srtmerg(qr, r, size, compar); i = 0; j = l; while(i < l && j < nelem) { if (compar(ql, qr) <= 0) { memcpy(qb, ql, size); qb += size; ql += size; ++i; } else { memcpy(qb, qr, size); qb += size; qr += size; ++j; } } if (i < l) { memcpy(qb, ql, size * (l - i)); } free(qt); return; }