Question

Using the C programming language implement Heapsort in the manner described in class. Here is some...

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.

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

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

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

            printf("fail\n");
            goto end;
        }
    }

    printf("pass\n");
#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 <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 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 <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], *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 <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 *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;
}
Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Here i am providing the code. Hope it helps, please give me a like. it helps me a lot.

main.c

/*
*
* 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("%f\n", a[i]);
    }
#else
    for (int i = 0; i < nelem - 1; ++i) {
      
        if (a[i] > a[i + 1]) {
          
            printf("fail\n");
            goto end;
        }
    }
  
    printf("pass\n");
#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;
}

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

srtbubb.c

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


srtheap.c

/**
* srtheap.c file
*
* to compile with heap sort:
*     gcc -std=c99 -DRAND -DTYPE=double -DHEAP *.c
*
*/
#include <stdlib.h>
#include <string.h>
#include "srt.h"

void heapify(char *array, size_t nelem, size_t size, size_t parent, int (*compar)(const void *, const void *));

void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
char *array;
size_t i;

/* build heap */
array = malloc((size + 1) * nelem);
memcpy(array + size, base, nelem * size);

for (i = nelem / 2; i >= 1; i--) {
    heapify(array, nelem, size, i, compar);
}

/* sort */
for (i = nelem; i > 1; i--) {
    /* move the largest one to the last position */
    swap(array + size, array + i * size, size);
    heapify(array, i - 1, size, 1, compar);
}

memcpy(base, array + size, nelem * size);
free(array);

}


void heapify(char *array, size_t nelem, size_t size, size_t parent, int (*compar)(const void *, const void *)) {
size_t child;
while ((child = 2 * parent) <= nelem) {
    if (child + 1 <= nelem && compar(array + child * size, array + (child + 1) * size) < 0) {
      child = child + 1; /* right child is larger */
    }
    if (compar(array + parent * size, array + child * size) < 0) {
      swap(array + parent * size, array + child * size, size); /* child is larger, swap */
      parent = child;
    } else {
      break;
    }
}
}

strinsr.c

/*
*
* 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], *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

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

Thank you, please like.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Implement and demonstrate a disk-based buffer pool class based on the LRU buffer pool replacement strategy....
Implement and demonstrate a disk-based buffer pool class based on the LRU buffer pool replacement strategy. Disk blocks are numbered consecutively from the beginning of the file with the first block numbered as 0. Assume that blocks are 4096 bytes in size. Use the supplied C++ files to implement your LRU Buffer Pool based on the instructions below. • Implement a BufferBlock class using the supplied BufferBlockADT.h o Your Buffer Block must inherit BufferBlockADT or you will not get credit...
IN C PROGRAMMING A Tv_show structure keeps track of a tv show’s name and the channels...
IN C PROGRAMMING A Tv_show structure keeps track of a tv show’s name and the channels (integer values) that broadcast the show. For this problem you can ONLY use the following string library functions: strcpy, strlen, strcmp. You MAY not use memcpy, memset, memmove. You can assume memory allocations are successful (you do not need to check values returned by malloc nor calloc). typedef struct tv_show { char *name; int num_channels, *channels; } Tv_show; a. Implement the init_tv_show function that...
Please answer the following C question: Read the following files called array-utils5A.c and array-utils5A.h. Build an...
Please answer the following C question: Read the following files called array-utils5A.c and array-utils5A.h. Build an executable with gcc -Wall -DUNIT_TESTS=1 array-utils5A.c The definitions for is_reverse_sorted and all_different are both defective. Rewrite the definitions so that they are correct. The definition for is_alternating is missing. Write a correct definition for that function, and add unit tests for it, using the unit tests for is_reverse_sorted and all_different as models. Please explain the logic errors present in in the definition of is_reverse_sorted...
C LANGUAGE IMPLEMENTATION - Writing source files implement several functions, declared in student.h, transcript.h and internal.h...
C LANGUAGE IMPLEMENTATION - Writing source files implement several functions, declared in student.h, transcript.h and internal.h (with support from common.h). There are 3 rules: 1. There are three types of students: undergraduate, MEng and PhD. 2. Undergraduates must complete 40 courses, MEng students 5 and PhD students 2. 3. Undergraduate students require a mark of 50 to pass; graduate students need a 65. ----------------Common.h-------------------------------------------------------------------------------------------------------------------------------------------------------------- #ifndef COMMON_H #define COMMON_H /*Portable macros for declaring C functions visible to C++.*/ #ifdef __cplusplus #define...
The code is in C programming language pls convert it into python. Thanks. Program --> #include...
The code is in C programming language pls convert it into python. Thanks. Program --> #include <stdio.h> #include <stdlib.h> void main() { //declare variables FILE *fileptr; char filename[15]; char charRead; char filedata[200],searchString[50]; int i=0,j=0,countNoOfWord=0,count=0; //enter the filename to be opened printf("Enter the filename to be opened \n"); scanf("%s", filename); /* open the file for reading */ fileptr = fopen(filename, "r"); //check file exit if (fileptr == NULL) { printf("Cannot open file \n"); exit(0); } charRead = fgetc(fileptr); //read the string...
This is C programming assignment. The objective of this homework is to give you practice using...
This is C programming assignment. The objective of this homework is to give you practice using make files to compose an executable file from a set of source files and adding additional functions to an existing set of code. This assignment will give you an appreciation for the ease with which well designed software can be extended. For this assignment, you will use both the static and dynamic assignment versions of the matrix software. Using each version, do the following:...
- implement the Stack ADT using the linked list approach. Use C++ program language #include "StackLinked.h"...
- implement the Stack ADT using the linked list approach. Use C++ program language #include "StackLinked.h" template StackLinked::StackLinked (int maxNumber) { } template StackLinked::StackLinked(const StackLinked& other) { } template StackLinked& StackLinked::operator=(const StackLinked& other) { } template StackLinked::~StackLinked() {    clear(); } template void StackLinked::push(const DataType& newDataItem) throw (logic_error) {    } template DataType StackLinked::pop() throw (logic_error) { } template void StackLinked::clear() {    StackNode* t;    while ( top != NULL)    {        t = top;       ...
Using the following code perform ALL of the tasks below in C++: ------------------------------------------------------------------------------------------------------------------------------------------- Implementation: Overload input...
Using the following code perform ALL of the tasks below in C++: ------------------------------------------------------------------------------------------------------------------------------------------- Implementation: Overload input operator>> a bigint in the following manner: Read in any number of digits [0-9] until a semi colon ";" is encountered. The number may span over multiple lines. You can assume the input is valid. Overload the operator+ so that it adds two bigint together. Overload the subscript operator[]. It should return the i-th digit, where i is the 10^i position. So the first...
Complete the following C program to solve the parenthesis matching problem using a stack. We studied...
Complete the following C program to solve the parenthesis matching problem using a stack. We studied the problem and the algorithm in class. Given a sequence of chars (symbols), check if each “(”, “{”, or “[” is paired with a matching “)”, “}”, or “[”. For example, correct: ( )(( )){([( )])}     correct: (( )(( ))){([( )])}   incorrect: )(( )){([( )])}     incorrect: ({[ ])}     incorrect: (   #include <stdio.h> #include <stdlib.h> #define size 100 void push(char *s, int* top, char element);...
C++ PROGRAM When I input 3 S P R, it was suppoesed to pop up L...
C++ PROGRAM When I input 3 S P R, it was suppoesed to pop up L W T. But it showed L L L.IDK why the moveNo is not working. I am asking for help, plz dont put some random things on it. main.cpp #include <iostream> #include "computer.h" #include "human.h" #include "referee.h" using namespace std; int main() {     human h;     computer c;     referee r;     r.compare(h,c);     return 0; } computer.cpp #include<iostream> #include "computer.h" using namespace std;...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT