Programming Tutorials

qsort() sample program in C++

By: Norman Chap in C++ Tutorials on 2007-09-17  

At times you may want to sort a table or an array; qsort() provides a quick and easy way to do so. The hard part of using qsort() is setting up the structures to pass in.

qsort() takes four arguments. The first is a pointer to the start of the table to be sorted (an array name works just fine), the second is the number of elements in the table, the third is the size of each element, and the fourth is a pointer to a comparison function.

The comparison function must return an int, and must take as its parameters two constant void pointers. void pointers aren't used very often in C++, as they diminish the type checking, but they have the advantage that they can be used to point to items of any type. If you were writing your own qsort() function, you might consider using templates instead. Listing below illustrates how to use the standard qsort() function.

Using qsort().

1:     /* qsort example */
2:
3:     #include <iostream.h>
4:     #include <stdlib.h>
5:
6:     // form of sort_function required by qsort
7:     int sortFunction( const void *intOne, const void *intTwo);
8:
9:     const int TableSize = 10;  // array size
10:
11:    int main(void)
12:    {
13:       int i,table[TableSize];
14:
15:       // fill the table with values
16:       for (i = 0; i<TableSize; i++)
17:       {
18:          cout << "Enter a number: ";
19:          cin >> table[i];
20:       }
21:       cout << "\n";
22:
23:       // sort the values
24:       qsort((void *)table, TableSize, sizeof(table[0]), sortFunction);
25:
26:       // print the results
27:       for (i = 0; i < TableSize; i++)
28:          cout << "Table [" << i << "]: " << table[i] << endl;
29:
30:       cout << "Done." << endl;
31:     return 0;
32:    }
33:
34:    int sortFunction( const void *a, const void *b)
35:    {
36:       int intOne = *((int*)a);
37:       int intTwo = *((int*)b);
38:       if (intOne < intTwo)
39:          return -1;
40:       if (intOne == intTwo)
41:          return 0;
42:       return 1;
43: }
Output: Enter a number: 2
Enter a number: 9
Enter a number: 12
Enter a number: 873
Enter a number: 0
Enter a number: 45
Enter a number: 93
Enter a number: 2
Enter a number: 66
Enter a number: 1

Table[0]: 0
Table[1]: 1
Table[2]: 2
Table[3]: 2
Table[4]: 9
Table[5]: 12
Table[6]: 45
Table[7]: 66
Table[8]: 93
Table[9]: 873
Done.

Analysis: On line 4, the standard library header is included, which is required by the qsort() function. On line 7, the function sortFunction() is declared, which takes the required four parameters.

An array is declared on line 13 and filled by user input on lines 16-20. qsort() is called on line 24, casting the address of the array name table to be a void*.

Note that the parameters for sortFunction are not passed to the call to qsort(). The name of the sortFunction, which is itself a pointer to that function, is the parameter to qsort().

Once qsort() is running, it will fill the constant void pointers a and b with each value of the array. If the first value is smaller than the second, the comparison function must return -1. If it is equal, the comparison function must return 0. Finally, if the first value is greater than the second value, the comparison function must return 1. This is reflected in the sortFunction(), as shown on lines 34 to 43.