There was a few either out dated, or incomplete questions similar, but no real a
ID: 3855476 • Letter: T
Question
There was a few either out dated, or incomplete questions similar, but no real answer to the proper question given the main function.
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 algorithm, both the comparison and main functions have been provided.
Code:
/*
*
* 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;
}
/*
*
* 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 */
Explanation / Answer
Answer for your question:
I understand that by looking at your comments and problem statement that please place these two functions definations inside main.c file and place the function declartion of these two functions inside SRT_H header file,
The below code is implemented based on problem statement i.e heap sort alagorthim, with helper function, see the below srtheap and sift functions to support function:
void sift( void * base, size_t size, int root, int bottom, int (*compar)( const void *, const void * ) ) {
int maxC;
void *temp;
temp= malloc( size );
maxC= root + root + 1;
if ( maxC < bottom ) {
int otherC= maxC + 1;
maxC= compar( ((char*) base) + otherC*size, ((char*) base) + maxC*size ) > 0? otherC : maxC;
} else if ( maxC > bottom ) return;
if ( compar( ((char*) base) + root*size, ((char*) base) + maxC*size ) >= 0 ) return;
memcpy( temp, ((char*) base) + root*size, size );
memcpy( ((char*) base) + root*size, ((char*) base) + maxC*size, size );
memcpy( ((char*) base) + maxC*size, temp, size );
sift( base, size, maxC, bottom, compar );
free( temp );
return;
}
void srtheap( void * base, size_t nelem, size_t size, int (*compar)( const void *, const void * ) ) {
int i;
void *temp;
temp= malloc( size );
for ( i= nelem/2; i >= 0; --i )
sift( base, size, i, nelem-1, compar );
for ( i= nelem-1; i >= 1; --i ) {
memcpy( temp, base, size );
memcpy( base, ((char*) base) + i*size, size );
memcpy( ((char*) base) + i*size, temp, size );
sift( base, size, 0, i-1, compar );
}
free( temp );
return;
}
/*int floatcompare( const void * a, const void * b ) {
if ( * (double *) a > * (double *) b ) return 1;
return * (double *) a < * (double *) b? -1 : 0;
}*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.