449,173 Members | 1,049 Online Need help? Post your question and get tips & solutions from a community of 449,173 IT Pros & Developers. It's quick & easy.

# qsort(...) in <stdlib.h>

 P: n/a can someone tell me how qsort function in is used (qsort(..........))? the function has a buffer, two void * parameters and the a pointer to a compare function. Thanks. Nov 14 '05 #1
5 Replies

 P: n/a Steve wrote: can someone tell me how qsort function in is used (qsort(..........))? the function has a buffer, two void * parameters and the a pointer to a compare function. Thanks. Have you tried man qsort? Good Luck! Rich Nov 14 '05 #2

 P: n/a On Sat, 04 Sep 2004 22:48:52 GMT, "Steve" wrote in comp.lang.c: can someone tell me how qsort function in is used (qsort(..........))? the function has a buffer, two void * parameters and the a pointer to a compare function. Thanks. Doesn't your C book cover it? Perhaps you need a better one. Also you have the arguments quite wrong. The prototype is: void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *)); The four arguments are: 1. A pointer to the beginning of an array of objects to be sorted. 2. The number of objects in the array. 3. The size of each object, in bytes. 4. A pointer to a function which accepts pointers to two objects contained in the array and will not change them, and returns an int indicating how the two objects compare against each other. qsort() is a generalized library function for sorting an array of objects. Generalized sorting algorithms are completely independent of the type or meaning of the data being sorted. The data independent algorithm of the sort can be turned into a function, and that is what qsort() is. The basic operations of sorting an array of objects are: 1. Compare two object in the array. 2. If the comparison indicates that they are out of order, then swap them. So a data independent function like qsort() can be turned into a sort routine for a specific array of objects by giving it the following information: 1. The location of the array of objects. 2. The number of objects in the array. 3. The size of each object in bytes, needed to swap out-of-order objects. 4. Some way to compare two objects. The fact that the caller supplies a comparison function allows one to sort the same data according to different values, for example name or employee number, just by passing different comparison functions. -- Jack Klein Home: http://JK-Technology.Com FAQs for comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html comp.lang.c++ http://www.parashift.com/c++-faq-lite/ alt.comp.lang.learn.c-c++ http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html Nov 14 '05 #3

 P: n/a "Steve" writes: can someone tell me how qsort function in is used (qsort(..........))? the function has a buffer, two void * parameters and the a pointer to a compare function. Thanks. Have you tried reading a reference manual? Here's what the GNU C library manual says about qsort(). Defining the Comparison Function ================================ In order to use the sorted array library functions, you have to describe how to compare the elements of the array. To do this, you supply a comparison function to compare two elements of the array. The library will call this function, passing as arguments pointers to two array elements to be compared. Your comparison function should return a value the way `strcmp' (*note String/Array Comparison::) does: negative if the first argument is "less" than the second, zero if they are "equal", and positive if the first argument is "greater". Here is an example of a comparison function which works with an array of numbers of type `double': int compare_doubles (const void *a, const void *b) { const double *da = (const double *) a; const double *db = (const double *) b; return (*da > *db) - (*da < *db); } The header file `stdlib.h' defines a name for the data type of comparison functions. This type is a GNU extension. int comparison_fn_t (const void *, const void *); Array Sort Function =================== To sort an array using an arbitrary comparison function, use the `qsort' function. The prototype for this function is in `stdlib.h'. - Function: void qsort (void *ARRAY, size_t COUNT, size_t SIZE, comparison_fn_t COMPARE) The QSORT function sorts the array ARRAY. The array contains COUNT elements, each of which is of size SIZE. The COMPARE function is used to perform the comparison on the array elements. This function is called with two pointer arguments and should return an integer less than, equal to, or greater than zero corresponding to whether its first argument is considered less than, equal to, or greater than its second argument. *Warning:* If two objects compare as equal, their order after sorting is unpredictable. That is to say, the sorting is not stable. This can make a difference when the comparison considers only part of the elements. Two elements with the same sort key may differ in other respects. If you want the effect of a stable sort, you can get this result by writing the comparison function so that, lacking other reason distinguish between two elements, it compares them by their addresses. Note that doing this may make the sorting algorithm less efficient, so do it only if necessary. Here is a simple example of sorting an array of doubles in numerical order, using the comparison function defined above (*note Comparison Functions::): { double *array; int size; ... qsort (array, size, sizeof (double), compare_doubles); } The `qsort' function derives its name from the fact that it was originally implemented using the "quick sort" algorithm. The implementation of `qsort' in this library might not be an in-place sort and might thereby use an extra amount of memory to store the array. -- "Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." --Brian Kernighan Nov 14 '05 #4

 P: n/a "Steve" wrote in message news:oD***************@newsread3.news.pas.earthlin k.net... can someone tell me how qsort function in is used (qsort(..........))? the function has a buffer, two void * parameters and the a pointer to a compare function. Thanks. #include #include #include struct person { char name; unsigned int age; }; void show(FILE *fp, const struct person *ppl, size_t count, const char *prefix) { size_t i = 0; fputs(prefix, fp); for(i = 0; i < count; ++i) fprintf(fp, "%-20s %u\n", ppl[i].name, ppl[i].age); } int by_name_ascending(const void *lhs, const void *rhs) { return strcoll(((struct person *)lhs)->name, ((struct person *)rhs)->name); } int by_name_descending(const void *lhs, const void *rhs) { return strcoll(((struct person *)rhs)->name, ((struct person *)lhs)->name); } int by_age_ascending(const void *lhs, const void *rhs) { return ((struct person *)lhs)->age - ((struct person *)rhs)->age; } int by_age_descending(const void *lhs, const void *rhs) { return ((struct person *)rhs)->age - ((struct person *)lhs)->age; } int main() { struct person folks[] = { {"William", 21}, {"John", 42}, {"Mary", 35}, {"Albert", 75}, {"Debbie", 12}, }; const size_t elems = sizeof folks / sizeof *folks; show(stdout, folks, elems, "unsorted:\n" "---------\n"); putchar('\n'); qsort(folks, elems, sizeof *folks, by_name_ascending); show(stdout, folks, elems, "Sorted by name in ascending order:\n" "----------------------------------\n"); putchar('\n'); qsort(folks, elems, sizeof *folks, by_age_ascending); show(stdout, folks, elems, "Sorted by age in ascending order:\n" "----------------------------------\n"); putchar('\n'); qsort(folks, elems, sizeof *folks, by_name_descending); show(stdout, folks, elems, "Sorted by name in descending order:\n" "----------------------------------\n"); putchar('\n'); qsort(folks, elems, sizeof *folks, by_age_descending); show(stdout, folks, elems, "Sorted by age in descending order:\n" "----------------------------------\n"); return 0; } -Mike Nov 14 '05 #5

 P: n/a "Steve" wrote in message news:... can someone tell me how qsort function in is used (qsort(..........))? the function has a buffer, two void * parameters and the a pointer to a compare function. Thanks. /* qsort - sort a table of data AUTHOR: Gregory Pietsch SYNOPSIS #include void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); DESCRIPTION The functionality described on this reference page is aligned with the ISO C standard. Any conflict between the requirements described here and the ISO C standard is unintentional. This volume of IEEE Std 1003.1-2001 defers to the ISO C standard. The qsort() function shall sort an array of nel objects, the initial element of which is pointed to by base. The size of each object, in bytes, is specified by the width argument. The contents of the array shall be sorted in ascending order according to a comparison function. The compar argument is a pointer to the comparison function, which is called with two arguments that point to the elements being compared. The application shall ensure that the function returns an integer less than, equal to, or greater than 0, if the first argument is considered respectively less than, equal to, or greater than the second. If two members compare as equal, their order in the sorted array is unspecified. RETURN VALUE The qsort() function shall not return a value. ERRORS No errors are defined. */ #include #include #define MAX_BUF 256 static void _Swap(char *qi, char *qj, size_t width) { char buf[MAX_BUF]; while (width > MAX_BUF) { memcpy(buf, qi, MAX_BUF); memcpy(qi, qj, MAX_BUF); memcpy(qj, buf, MAX_BUF); qi += MAX_BUF; qj += MAX_BUF; width -= MAX_BUF; } if (width > 0) { memcpy(buf, qi, width); memcpy(qi, qj, width); memcpy(qj, buf, width); } } void (qsort)(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)) { size_t i, j; char *qi, *qj, *qp; switch (nel) { case 0: case 1: return; /* doesn't have to be sorted */ case 2: case 3: case 4: /* Bubble sort is probably easier with four elements or less */ qp = base; for (i = 0; i < nel - 1; i++) { for (j = i + 1; j < nel; j++) { qi = qp + (i * width); qj = qp + (j * width); if ((*compar)(qi, qj) > 0) _Swap(qi, qj, width); } } return; default: while (1 < nel) { i = 0; j = nel - 1; qi = base; qj = qi + j * width; qp = qj; while (i < j) { /* partition about pivot */ while (i < j && (*compar)(qi, qp) <= 0) { i++; qi += width; } while (i < j && (*compar)(qp, qj) <= 0) { j--; qj -= width; } if (i < j) _Swap(qi, qj, width); } if (qi != qp) _Swap(qi, qp, width); j = nel - i; if (j < i) { /* recurse on smaller partition */ if (1 < j) qsort(qi, j, width, compar); nel = i; } else { /* lower partition is smaller */ if (1 < i) qsort(base, i, width, compar); base = qi; nel = j; } } } } /* END OF FILE */ Nov 14 '05 #6

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

Browse more C / C++ Questions on Bytes 