Sorting arrays of pointers with qsort
Jan. 10th, 2011 07:45 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sawylWhilst attempting to sort an array of pointers to structures using the standard
The reason, once I'd troubled myself to think about it for a while, was obvious. The sort routine passes two values to the comparison function in a type-independent way using void pointers to reference to the original data. This makes it possible to compare data of any type by allowing the programmer to cast the void pointers back to the original type before checking the values of the two arguments.
Thus, when using qsort to order an array of integers, the comparison function receives a pair of pointers to integers in the original array and these can be cast back to standard integer pointers in order to reference their values. So it follows that when the array being sorted contains a set of pointers to a structure , these will be cast to void pointers before passed to the comparison function — because qsort doesn't know that they're already pointers — which means that the arguments will be pointers to pointers and not pointers to the original structure. Which means that if the data is being sorted according to one of the elements of the structure, it is necessary to chase the pointers passed to the comparison function through two levels of indirection rather than just one.
QED.
qsort() library function, I was caught out by the data types of the two arguments passed to the comparison function by the sort routine. I'd been expecting these to be pointers to my structures and cast them accordingly, whereas they were actually pointers to pointers to structures, and consequently my elements came out in the wrong order.The reason, once I'd troubled myself to think about it for a while, was obvious. The sort routine passes two values to the comparison function in a type-independent way using void pointers to reference to the original data. This makes it possible to compare data of any type by allowing the programmer to cast the void pointers back to the original type before checking the values of the two arguments.
Thus, when using qsort to order an array of integers, the comparison function receives a pair of pointers to integers in the original array and these can be cast back to standard integer pointers in order to reference their values. So it follows that when the array being sorted contains a set of pointers to a structure , these will be cast to void pointers before passed to the comparison function — because qsort doesn't know that they're already pointers — which means that the arguments will be pointers to pointers and not pointers to the original structure. Which means that if the data is being sorted according to one of the elements of the structure, it is necessary to chase the pointers passed to the comparison function through two levels of indirection rather than just one.
QED.
