Using the C programming language implement Heapsort in the manner described in c
ID: 3856814 • Letter: U
Question
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. Now i am extremely confused on how to execute this properly given what program we use to "build" and run. I will describe exactly what i have.
2 Files as follows.
Main.c
/*
*
* main.c file
*
*/
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#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;
}
2nd File:
srt.h:
/*
*
* srt.h file
*
*/
#ifndef SRT_H
#define SRT_H
#include <string.h>
#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 */
Now my question involves what the solution to this problem is. An issue for me that might pop up, is where im placing the "answer" provided within the code. does it go in the Main file? Or do i create seperate files.. I would really appreciate a solution and describe how exactly to properly execute it. Thank you so much in advance!
Explanation / Answer
Yes you need to create separate files for each sorting function....
#ifndef SRT_H
#define SRT_H
#include <string.h>
#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 <limits.h>
#include <stdio.h>
#include <stdlib.h>
#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 <stdbool.h>
#include <stddef.h>
#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 isSort = true;
for (size_t j = 0; j < i; ++j) {
char *tempQ = (char *)base + size * j;
char *tempN = tempQ + size;
if (compar(tempQ, tempN) > 0) {
swap(tempQ, tempN, size);
isSort = false;
}
}
if (isSort) {
break;
}
}
return;
}
/*
*
* srtinsr.c file
*
*/
#include <stdlib.h>
#include <string.h>
#include "srt.h"
void srtinsr(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
char buf[size], *_base = base;
for (size_t i = 1; i < nelem; ++i) {
memcpy(buf, _base + size * i, size);
size_t j = i;
while (j > 0 && compar(buf, _base + size * (j - 1)) < 0) {
memcpy(_base + size * j, _base + size * (j - 1), size);
--j;
}
memcpy(_base + size * j, buf, size);
}
return;
}
/*
*
* srtmerg.c file
*
*/
#include <stdlib.h>
#include <string.h>
#include "srt.h"
void srtmerg(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
char *_base = base, *_left, *_right, *qt;
size_t i, j, l, r;
if (nelem <= 1) {
return;
}
else if (nelem == 2) {
if (compar(_base, _base + size) > 0) {
swap(_base, _base + size, size);
}
return;
}
l = nelem / 2;
r = nelem - l;
_left = qt = malloc(size * l);
memcpy(_left, _base, size * l);
_right = _base + size * l;
srtmerg(_left, l, size, compar);
srtmerg(_right, r, size, compar);
i = 0; j = l;
while(i < l && j < nelem) {
if (compar(_left, _right) <= 0) {
memcpy(_base, _left, size);
_base += size;
_left += size;
++i;
}
else {
memcpy(_base, _right, size);
_base += size;
_right += size;
++j;
}
}
if (i < l) {
memcpy(_base, _left, size * (l - i));
}
free(qt);
return;
}
/*
*
* srtheap.c file
*
*/
#include <stdlib.h>
#include <string.h>
#include "srt.h"
void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
int j;
char *tempFirst = (char *)base;
int c = 1
for (j = nelem - 1; j >= 0; j--)
{
char *tempQ = (char *)base + size * j;
char *temp = tempQ + size;
temp = tempQ;
tempFirst = tempQ /* swap max element with rightmost leaf element */
tempQ = temp;
do
{
c = 2 * tempFirst + 1;
char *tempc = (char *)base + size * c;
char *tempc1 = (char *)base + size * (c+1);
if ((compar(_base+size, _base + size+1)) && c < j-1)
c++;
if ((compar(_base, _base + size+c)) && c<j)
{
temp = tempFirst;
tempFirst = tempc;
tempc = temp;
}
tempFirst = c;
} while (c < j);
}
return;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.