Thread: How to Qsort an array of structs by one of its members?

  1. #1
    Registered User Vespasian's Avatar
    Join Date
    Aug 2011
    Posts
    181

    How to Qsort an array of structs by one of its members?

    I am versed in qsorting struct members within a struct instance, as in the example below:

    Code:
    #include <iostream>
    #include <stdlib.h>
    
    using namespace std;
    
    struct item_database {
        int data1[8]={1,4,4,3,5,6,4,4};
        int data2[8]={1,7,6,3,4,2,11,11};
    }a;
    
    int compare (const void* element1, const void* element2)
    {
        if(*(int*)element1 >= *(int*)element2)
            return -1;
        else
            return 1;
    }
    
    int main()
    {
        item_database a;
        item_database* aptr = &a;
        qsort(aptr->data1,8, sizeof(int), compare);
        cout << a.data1[1] << endl;
        return 0;
    }
    What I CANT do however is to sort an array of structs by one of its members. This is a complete different problem even if it sounds similar.

    In other words, the problem is this; Say we have a struct:

    Code:
    struct item_database {
        int key;
        string token;
    };
    Then we declare an array of this struct in the heap:
    Code:
        item_database *idptr = new item_database[700000];
    and initialize its values.

    How would one go about sorting this heap array of structs by its member function "token"?

    I used the following call to qsort (standard library) and call to the compare function but it doesnt work:

    Code:
        qsort (idptr, 1000, sizeof(string), compare);
    Code:
    int compare (const void* a, const void* b)
    {
        if (*(char*)a >= *(char*)b)
            return 1;
        else
            return -1;
    }
    Or in more lamens terms say we have the following stuct instances:
    Key: Token:
    1 Hello
    2 World
    3 How
    4 Are
    5 You

    Then I need those structs to order according to token (alphabetically, increasing or decreasing depending whats in our compare function)
    Last edited by Vespasian; 03-31-2013 at 11:16 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,313
    Instead of using qsort, use std::sort. Your compare function could then become:
    Code:
    bool compare(const item_database& a, const item_database& b)
    {
        return a.token < b.token;
    }
    Or you could use a lambda instead, if possible.

    Generally, unless you have some special reason, you should prefer std::sort to qsort.
    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

  3. #3
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    I have the feeling that qsort is used in C. Here I have implemented it.

    As a result, I would suggest you to use std::sort. I have implement this too, here. Of course, you have to modify a bit the code for your needs. (the compar function).

    In order for you to understand how unusual is for someone to use qsort in cpp, when I saw the title of the thread I thought you had posted C code in the wrong thread.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Even your compare function for ints is wrong. It is returning -1 for items which are equal, when it must return zero in that case.
    That will cause it to sort incorrectly in some cases.

    Use use std::sort instead, as described.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. qsort not sorting structs
    By ArcadeEdge in forum C Programming
    Replies: 6
    Last Post: 04-11-2012, 05:44 AM
  2. Structs, members, and casting
    By Nick Howes in forum C Programming
    Replies: 4
    Last Post: 03-05-2008, 12:54 PM
  3. Throw away members in qsort
    By xxxrugby in forum C Programming
    Replies: 4
    Last Post: 04-24-2005, 06:08 AM
  4. Typedefining members of structs
    By Verdagon in forum C++ Programming
    Replies: 18
    Last Post: 04-03-2005, 02:06 PM