Thread: How to sort an struct of parabolas after their vertex height, using qsort?

  1. #1
    Registered User
    Join Date
    Jan 2021
    Posts
    2

    How to sort an struct of parabolas after their vertex height, using qsort?

    I got a problem where I have to first create a function that calculates the vertex height of a given struct of parabolas and returns 0 for parabola und 1 if not. Then sort them with qsort using the vertex height as parameter which ascends. Also if a == 0 (not a parabola), those will be sorted after the parabolas. Then I have to use a test-main to print example-parabolas and see if they got sorted correctly. Global variables are not allowed.

    I think I got the calculation of vertex height, but I have no clue what I have to write into the function for qsort, tutorials say that I have to compare a and b and return 1, -1 or 0, but I don't know how to "translate" that for my case. I'm kinda new to programming and have not quite gotten the concept of pointers or referncing functions in c.

    The given header.h

    Code:
    #ifndef header
    #define header 1
    
    struct parabola {
        double a;
        double b;
        double c;
    };
    
    int vertexheight(struct parabola * p, double *y);
    
    void sort_parabola(struct parabola * p, int n);
    
    
    #endif
    my program

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "header.h"
    
    int compare();
    
    
    int vertexheight(struct parabola * p, double *y) {
        int rc = 0;
            
        if (p->a == 0) {
            
            rc = 1;
        
        }   else {
        
            *y = p->c - ((p->b*p->b) / (4*p->a));
        }     
          
        return rc;
    }
    
    int compare(const void * a, const void * b) {
    
    
        //?
        
        return 0;
        
    }
    
    
    void sort_parabola(struct parabola * p, int n) {
        
        qsort(p, n, sizeof(struct parabola), compare);  
        
    }
    
    int main() {
            
        struct parabola p[] = {
            {1,2,3},
            {2,5,-19}, {0,-100,-56}, {-967,24,-24}, {36,2,70},
            {5,72,0}, {75,-4,55}, {20,41,7},
            {-1,0,0}
        };
        double y;
        int i, size = sizeof(p) / sizeof(struct parabola);
        
        
        sort_parabola(p, sizeof(p) / sizeof(struct parabola)); 
     
        for (i = 0; i < size; i++){
            
            //output
            
        }
          
        return 0;
    }

    The sorted output should be something like this:

    Code:
    [0]
    {5.000000,72.000000,0.000000},
    y=-259.200000
    
    
    [1]
    {-967.000000,24.000000,-24.000000},
    y=-23.851086
    
    
    [2]
    {2.000000,5.000000,-19.000000},
    y=-22.125000
    
    
    [3]
    {20.000000,41.000000,7.000000},
    y=-14.012500
    
    
    [4]
    {-1.000000,0.000000,0.000000},
    y=0.000000
    
    
    [5]
    {1.000000,2.000000,3.000000},
    y=2.000000
    
    
    [6]
    {75.000000,-4.000000,55.000000},
    y=54.946667
    
    
    [7]
    {36.000000,2.000000,70.000000},
    y=69.972222
    Thanks a lot if someone can help me with this!

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,629
    Your compare function would start something like this.
    Code:
    int compare(const void * a, const void * b) {
      const struct parabola *pa = a;
      const struct parabola *pb = b;
      double ha, hb;  // heights
      int ra, rb; // returns
      ra = vertexheight(pa, &ha);
      rb = vertexheight(pb, &hb);
      // now you compare things.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jan 2021
    Posts
    2
    Thanks for your answer! If I compare it like this, the output is not sorted properly. Also my compiler
    gives me a warning: expected 'struct parabola *' but argument is of type 'const struct parabola *'
    I have to use -Wall

    Guess I did something wrong?
    Also, how do I sort the parabolas with a == 0 at the end of the list? These have no vertexheight, because they are not parabolas.

    Code:
    int compare(const void * a, const void * b) {
    
    
        const struct parabola *pa = a;
          const struct parabola *pb = b;
           
        double ha, hb;  // heights
          int ra, rb; // returns
          ra = vertexheight(pa, &ha);
         rb = vertexheight(pb, &hb);
         
          if (ra < rb) return -1;
          if (ra > rb) return 1;
          if (ra == rb)return 0;
        
        
        return 0;
        
    }

    Code:
    int main() {
            
        struct parabola p[] = {
            {1,2,3},
            {2,5,-19}, {0,-100,-56}, {-967,24,-24}, {36,2,70},
            {5,72,0}, {75,-4,55}, {20,41,7},
            {-1,0,0}
        };
        double y;
        int i, size = sizeof(p) / sizeof(struct parabola);
        
        sort_parabola(p, sizeof(p) / sizeof(struct parabola)); 
     
        for (i = 0; i < size; i++){
            
            vertexheight(p+i, &y);
            printf("[%i]\n{%lf,%lf,%lf},\ns=%lf\n\n", i, p[i].a, p[i].b, p[i].c, y);
            y = 999;
        }
            
        
          
        return 0;
    }

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,314
    Quote Originally Posted by Moepius
    Also my compiler
    gives me a warning: expected 'struct parabola *' but argument is of type 'const struct parabola *'
    Your compiler is right: to compute the height, you don't need to modify the struct object, therefore this:
    Code:
    int vertexheight(struct parabola * p, double *y);
    should have been:
    Code:
    int vertexheight(const struct parabola * p, double *y);
    since you did not declare vertexheight to be const-correct, when you passed a const struct parabola pointer to it in the compare function, the compiler complained because from its perspective, it is possible that vertexheight might modify the struct object, whereas the const says that the struct object that the pointer points to should not be modified.

    Quote Originally Posted by Moepius
    Guess I did something wrong?
    Yes, your compare function is too simple. You're only sorting parabola vs non-parabola, without taking vertex height into account.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 8
    Last Post: 11-11-2014, 01:16 PM
  2. Array sort with qsort, by using two criteria?
    By tinchi in forum C Programming
    Replies: 6
    Last Post: 09-27-2014, 01:30 AM
  3. Use qsort() to sort array of pointers to struct
    By VIgnotam in forum C Programming
    Replies: 4
    Last Post: 04-04-2012, 06:42 PM
  4. Using qsort to sort an array of strings
    By MSF1981 in forum C Programming
    Replies: 31
    Last Post: 05-17-2009, 01:31 AM
  5. using qsort to sort an array of strings
    By bobthebullet990 in forum C Programming
    Replies: 6
    Last Post: 11-25-2005, 08:31 AM

Tags for this Thread