Can I use STL qsort() for sorting structure?
I have created an array of structure
And I need to sort this array of structure in ascending transnum.Code:struct structtid { int tid; //transaction id list int *tidptr; // pointer to the transaction int transnum; //size of each transaction };
Is it possible to do this?
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);
how about stl qsort()? does it allow me to sort structure?
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 06:23 AM.
ancient dragon, thanks for your help! =)
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
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.
now create an array of the above and sort it.Code:struct itemFrequency { int item; int frequency; };
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
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?
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
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.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]]);
Last edited by Ancient Dragon; 09-19-2005 at 08:28 PM.
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:Originally Posted by franziss
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.
ancient dragon, yea, i got a source code from a c++ textbook, hope its efficient enough... =)
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
