Implement heapsort in the manner described


Using the C programming language implement Heapsort in the manner described in class. Here is some example code to use as a guideline. Remember, you need only implement the sort (srtheap.c) algorithm, both the comparison and main functions have been provided.

/*
*
* 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"

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("%fn", a[i]);
}
#else
for (int i = 0; i < nelem - 1; ++i) {

if (a[i] > a[i + 1]) {

printf("failn");
goto end;
}
}

printf("passn");
#endif

end:

free(a);

return 0;
}

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;
}  

Request for Solution File

Ask an Expert for Answer!!
C/C++ Programming: Implement heapsort in the manner described
Reference No:- TGS093264

Expected delivery within 24 Hours