# Can I use STL qsort() for sorting structure?

• 09-17-2005
franziss
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?
• 09-17-2005
Ancient Dragon
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);

• 09-17-2005
franziss
how about stl qsort()? does it allow me to sort structure?
• 09-17-2005
Ancient Dragon
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;
}

• 09-17-2005
franziss
ancient dragon, thanks for your help! =)
• 09-19-2005
franziss
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
• 09-19-2005
Ancient Dragon
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.
• 09-19-2005
franziss
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
• 09-19-2005
franziss
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?
• 09-19-2005
Ancient Dragon
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.
• 09-19-2005
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().
• 09-19-2005
ComputerPhreak
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().
• 09-19-2005
Ancient Dragon
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.
• 09-19-2005
franziss
ancient dragon, yea, i got a source code from a c++ textbook, hope its efficient enough... =)
• 09-20-2005
Ancient Dragon
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