Hello, OnlineGDB Q&A section lets you put your programming query to fellow community users. Asking a solution for whole assignment is strictly not allowed. You may ask for help where you are stuck. Try to add as much information as possible so that fellow users can know about your problem statement easily.

I tried a lot to make the code work, but it's not working as there are errors. Can you please tell me what's wrong?

+10 votes
asked Aug 3, 2021 by npatel300 (1,440 points)
/*
 *
 *  srt.h file
 *
 */
#ifndef SRT_H
#define SRT_H
#include <string.h>
#include "srt.h"

float arr[1000000];
 void srtheap(void *, size_t, int (*)(const void *, const void *))
    {
    int n = 1000000;
    for(int i = n/2-1; i>=0; i--)
    srtheap(arr, n, i);
    
    for(int i = n - 1; i > 0; i--){
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        
        srtheap(arr, i, 0);
    }
}

  void maxheap(int arr[]){  
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if(left < nelem &&arr[left] > arr[largest])
    largest = left;
    if(right < nelem &&arr[right] > arr[largest])
    largest = right;
    if(largest!= i){
        srtheap(arr[i], nelem, largest);
    }   

srtheap(arr[i], nelem, sizeof(float), *float compare);

static float compare(const void *p1, const void *p2) {

    if (*(TYPE *)p1 < *(TYPE *)p2) {

        return -5;
    }
    else if (*(TYPE *)p1 > *(TYPE *)p2) {

        return +5;
    }

}

for (int i = 0; i < nelem - 1; ++i) {

    if (arr[i] > arr[i + 1])
    {
        printf("fail\n");
    }

    else if
        printf("pass\n");
}
}

#endif /* SRT_H */

1 Answer

+1 vote
answered Aug 4, 2021 by Peter Minarik (84,720 points)
edited Aug 4, 2021 by Peter Minarik

Hi npatel30,

I have checked the code you shared regarding this problem.

Summary

I spent quite a long time to make this easy for you. I came up with a project where everything is ready for you all you need to do is implement the sorting functions in srt.c file:

  • bubble sort
  • heap sort
  • insertion sort
  • merge sort

Actually, I've already implemented the bubble sort, just to demonstrate the project works.

The Details

The project you shared was a complete mess (variable names missing, mismatched opening/closing braces, etc). I needed to understand (and guess) what needs to be done here, what is given and what you tried to do.

I deduced that srt.h was given by your teacher. So I built upon this and removed all the confusing part.

srt.h

I figured this is the file that was given to you by your teacher, so I left this file unchanged.

Please note, in C you can crate a function prototype (declare a function) without specifying the name of your arguments. However, when you implement your functions (define the functions) you cannot omit the name, otherwise you won't be able to reference them. (Actually you can omit the name if you never want to use those parameters, but why do you have them in the first place them?)

srt.c

So this is the file where you need to implement the various sorting algorithms.

First of all, this file needs to include srt.h.

I've done the implementation for the bubble sort (that's the easiest one XD) just to demonstrate how everything would work. Note: I did just the naive implementation and not the most efficient algorithm. Feel free to make it better. ;)

All these functions modify the input buffer and reorder the elements there.

Function arguments

All the functions have the following arguments:

ParameterComment
void * bufferthe buffer where the array to be sorted is. Void type, so any sorting would work with any arbitrary type.
size_t elementSizeThe size of a single element of the array to be sorted
size_t elementCountThe number of elements in the array to be sorted
int (*compare)(const void *, const void *)The function (pointer) that compares two elements in the array. If the first element is greater, it returns >0; if the first element is smaller, it returns <0; if they are equal 0 is returned.

You can see how to access (the address of) an arbitrary member of the array: buffer + elementSize * j.

main.c

I created a main.c where there are 4 main functions:

  • TestBubbleSort()
  • TestHeapSort()
  • TestInsertionSort()
  • TestMergeSort()

These will test all the sorting implementations you need to do. Of course this is not an exhaustive test, feel free to apply more testing on your own.

However, I'd advise first to implement the sorting functions then do more testing.

Also, the main.c has some helper functions. You are free to explore them and see what they do, but you should first really focus on srt.c and implement the various sorting mechanisms.

The Test Data

I chose to test with float (4 bytes) and byte (1 byte) data types just to demonstrate that the generic sorting functions support any arbitrary element sorting, it is not tied to the size of the elements in the array.

Also, all the four test functions above start by duplicating the test data. This is for two reasons:

  1. this allows the same test data to be passed to all the testing functions
  2. duplication makes sure the original data would not change

Validation

I didn't go all the way to allow automatic test result validation i.e. notify the user if the sorting algorithms provided the wrong order.

For this after every test, you have to do your validation on your own. Look at the output, and check if the sorting algorithms indeed provided the right order.

Final Words

I think this project is very clear now. Testing is ready for you. Sort function stubs are ready, all you need to do is implement them.

So, here's the project, fork from it and do your own implementation. You can share the link to your changes (as you did before) when done.

Good luck!

commented Aug 5, 2021 by npatel300 (1,440 points)
Thank you for taking time and helping over my code. Can you please proofread if it is correct?
Here is the link of my code:
https://onlinegdb.com/pRPMwr6k4
commented Aug 5, 2021 by Peter Minarik (84,720 points)
Hi npatel300.

One usually compiles the code and tests if it does what it's meant to do.

I looked at your code. It compiles! Great!

I ran it, and it said PASS. That looks nice.

So after this, let's take a closer look at your code.

First of all, indentations are messed up. You should really increase the indentation at a new opening brace ({) and decrease them at a closing brace (}). It will allow one to easily see what belongs to the same scope.

If you had done that, you would see that in your main() you have a loop and after checking the first element, you return, not after the whole loop is done.

But there are more problems. Fundamental ones. You created 4 functions: maxheap, srtheap, FloatCompare and PrintFloatArray. But all of them are dead code, as they are never called. There is no code path starting from main() that ever reaches these functions.

Another fundamental problem is that you're not doing what your professor asked you to do. S/He gave you 4 function prototypes that you needed to implement. You only implemented one (srtheap), but you even changed the signature (one less argument in your implementation). So basically you didn't do what s/he asked you to do.

In the link above (see "project") everything is ready for you, all you have to do is edit the srt.c file and implement the sorting functions there. After that, you just need to run the project and check the output and validate if your sorting algorithm works correctly, that is, the output is correctly sorted for your algorithm.
commented Aug 5, 2021 by npatel300 (1,440 points)
But, my professor told us to implement only heap function, not the other ones. When I make a function call for heap, I do get an error. If you can help me fix it. Thank you
https://onlinegdb.com/6rC0s6IA1
commented Aug 5, 2021 by Peter Minarik (84,720 points)
edited Aug 5, 2021 by Peter Minarik
Ok, so you need to do only the heap sort.

All my other comments above still hold though.

I've looked your shared project: https://onlinegdb.com/6rC0s6IA1

The problem is that you still haven't cleaned up your code and indentations are a mess.

You meant the line

srtheap(a, nelem, sizeof(TYPE), compare);

to be an instruction within a function.

However, due to the messed up scopes (again, clear up your braces, where they begin, where they end, indent accordingly) it ended up being on the same level as any function declaration.

sizeof has no business being in a function declaration.

Move this line into the body of your desired function.

But first of all, clean up your code. Make sure every opening brace has a matching closing brace. Indent lines accordingly. (I personally prefer braces to be on empty lines, not after other code. It makes it harder for me to see them.)
commented Aug 5, 2021 by npatel300 (1,440 points)
for this call, srtheap(a, nelem, sizeof(TYPE), compare), I moved it to desired function, is this right now? I have also made changes to indentation and braces.
https://onlinegdb.com/G3uHJeZe7
commented Aug 6, 2021 by Peter Minarik (84,720 points)
No, it is not right. You keep changing the signature of the function. You're not implementing the same function your professor asked you. Your function has 3 parameters, the one assigned to you by the professor has 4.

Also, you do not use the array/buffer provided by the caller. Nor the comparison function. So  practically your function is useless to anyone as it won't sort their data.

People want to call srtheap like this:

srtheap(myArray, elementSize, elementCount, comparisonFunction);

(or elementCount first and elementSize after, but that is not clear from the function prototype as it does not contain variable names, just types).

And this would sort any array with any type of elements in it (as long there is a correct comparisonFunction provided for it).

******************************************************

All you have to do is this:

1. Open https://www.onlinegdb.com/702KdYYQq
2. For from this project (so you can edit it)
3. Open srt.c source file
4. Go to line 17 and do the heap sort implementation there. Do not change the function signature. Read my original post about the arguments of the function and what they mean.
5. When done, run the project and check the output if the heap sort section shows the numbers in ascending (increasing) order.
6. When all is good, you can copy that function from srt.c to any of your projects and your work is done. If that function works in the project I created for you, it will work everywhere.
Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.
...