Can I use STL qsort() for sorting structure?

This is a discussion on Can I use STL qsort() for sorting structure? within the C++ Programming forums, part of the General Programming Boards category; Can I use STL qsort() for sorting structure? I have created an array of structure Code: struct structtid { int ...

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    163

    Can I use STL qsort() for sorting structure?

    Can I use STL qsort() for sorting structure?
    I have created an array of structure

    Code:
    struct structtid
    {
      int tid; //transaction id list
      int *tidptr;  // pointer to the transaction
      int transnum; //size of each transaction
    };
    And I need to sort this array of structure in ascending transnum.

    Is it possible to do this?

  2. #2
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    if you put the stucture in vector, then you can use stl to sort it
    Code:
    bool comp(structid& t1, structid& t2)
    {
       return t1.tid < t2.tid ? true : false;
    }
    vector<structid> theList;
    sort(theList.begin(),theList.end(), comp);

  3. #3
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    how about stl qsort()? does it allow me to sort structure?

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    stl does not have qsort() -- that is a standard C function. But yes you can use it just like any C program. See your compiler's help or google for that function. You have to provide the comparison function similar to the one I posted.
    Code:
    int comp(const void* p1, const void* p2)
    {
       return ((structtid*)p1)->tid - ((structtid*)p2)->tid;
    }
    Last edited by Ancient Dragon; 09-17-2005 at 07:23 AM.

  5. #5
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    ancient dragon, thanks for your help! =)

  6. #6
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    I got a problem,
    I need to sort an array which contains the item e.g. Item = [1,2,3,4,5]
    and I got another array which is the item's frequency .e.g. Frequency [5,2,2,0,1]
    After sorting, the Item = [4,5,2,3,1]
    How to I use qsort() to do it? the last argument of qsort only allow me to take in Item as the arguement

  7. #7
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    you will probably have to create a structure to hold the item and its frequenty because the comparison function does not know which two items it is receiving from qsort.
    Code:
    struct itemFrequency
    {
       int item;
       int frequency;
    };
    now create an array of the above and sort it.

  8. #8
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    i got a thousands of arrays to sort and creating an array of structure is too memory expensive for me.

    my friend suggests that i should declare a global array which contain the frequencies whereby the comparison function that qsort take can access the global array to check for the item frequency

  9. #9
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    big mistake, I cannot access a global variable from the function comp
    Code:
    int *freq; //global variable containing p1 and p2 frequency
    int comp(const void* p1, const void* p2)
    {
       return freq[*(int*)p1] - freq[*(int*)p2];
    }

    why is it so?

  10. #10
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    the comparison function is called by qsort() -- your program should not call it directly. The two parameters are pointers into the array that you want sorted, the comparison function has no clue about which two elements of the array because its only purpose is to tell qsort whether p1 is less than, equal to, or greater than the second parameter p2. There is no way that the comparison function will find a global array of frequencies of any use.

    Considering your problem, you might want to write your own custom sort algorithm so that you can take advantage of indirect sort, sort one array without disturbing the order of the second. Using your previous example of item and frequency arrays, frequency can be sorted indirectly by sorting item. Using bubble sort algorithm (you will want a better algorithm), it might look like this
    Code:
    void sort(int item[], int itemsize, int frequency[], int freqsize)
    {
       for(int i = 0; i < itemsize-1; i++)
       {
           for(int j = i+1, j < itemsize; j++)
          {
               if( frequency[ item[i] ] < frequency [ item[j] ] )
              {
                 // swap item array elements
                 int temp = item[i];
                 item[i] = item[j];
                 item[j] = temp;
              }
        }
     }
    
    // display all the elemenets of frequency
    for(i = 0; i < itemsize; i++)
       printf("%d\n", frequency[item[i]]);
    you can easily find source code for lots of other better sort algorithms. Just plug one into your program and modify the comparisons to be similar to above.
    Last edited by Ancient Dragon; 09-19-2005 at 09:28 PM.

  11. #11
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    Ancient dragon, thanks for your help! Actually I got implement my own quick sort algo which you described above. But I think it will be slower than the qsort(), since it is coded by me... =)
    Thus I'm think of using qsort().

  12. #12
    Registered User
    Join Date
    Aug 2005
    Posts
    10
    Quote Originally Posted by franziss
    Ancient dragon, thanks for your help! Actually I got implement my own quick sort algo which you described above. But I think it will be slower than the qsort(), since it is coded by me... =)
    Thus I'm think of using qsort().
    I suggest doing the following instead of using qsort:
    Overload operator< on your structure, then use the stl's std::sort() to sort the list of your structures. I can pretty much guarantee you that it will be faster than qsort because the compiler will automatically inline operator<, therefore you won't incur the penalty of calling your custom compare() function using qsort().

  13. #13
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    Quote Originally Posted by ComputerPhreak
    Overload operator< on your structure, then use the stl's std::sort() to sort the list of your structures. I can pretty much guarantee you that it will be faster than qsort because the compiler will automatically inline operator<, therefore you won't incur the penalty of calling your custom compare() function using qsort().
    but std::sort has the same problem that qsort() has as described above. So both qsort() and std::sort are worthless for his purpose. He needs his own custom sort algorithm similar to the one I described.


    franziss: qsort() uses quickersort algorithm -- just google for quickersort and you will find the source code.

  14. #14
    Registered User
    Join Date
    Dec 2004
    Posts
    163
    ancient dragon, yea, i got a source code from a c++ textbook, hope its efficient enough... =)

  15. #15
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    google for "sort algorithms" and this is one of the many links. This is a ton of information on the net that you can use.

    http://linux.wku.edu/~lamonml/algor/sort/sort.html

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. no tree data structure in STL
    By manav in forum C++ Programming
    Replies: 2
    Last Post: 01-11-2008, 01:23 AM
  2. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 07:39 AM
  3. Replies: 7
    Last Post: 04-13-2003, 11:53 PM
  4. Serial Communications in C
    By ExDigit in forum Windows Programming
    Replies: 7
    Last Post: 01-09-2002, 10:52 AM
  5. C structure within structure problem, need help
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 11-30-2001, 05:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21