baileyc@boulder.Colorado.EDU (BAILEY CHRISTOPHER R) (04/10/90)
I'm not sure how to use qsort. I have an array, where only the end of it needs to be sorted (say the last 5 elements). The part that confuses me the most is the comparand. So, say my array is mapping[10] and I need to sort all the elements from mapping[4] to mapping [9]. How do I do this using qsort? Assumming that qsort is called like this: qsort(base, num, width, (compare)()); where: base = start of target array num = array size in elements width = element size in bytes compare function So, I would assume that my base would be mapping[4], that num would be 10, and that width would be sizeof(int), but what about compare? In my case, if mapping is [10], then the highest number that can be stored in this array is 9, only the numbers 0 - 9 could be used in this array, and each one only once. so mapping could look like: 1,3,5,9,8,2,7,6,0,4. How do I use compare? All the examples I've seen the compare doesn't make sense to me. Thanks... Chris Bailey :: baileyc@tramp.Colorado.EDU One Agro Mountain Biker - Dialed in for ultra gonzo badness! "No his mind is not for rent, to any god or government" - RUSH Member of Team Buck Naked of Buckingham Palace
chris@mimsy.umd.edu (Chris Torek) (04/14/90)
In article <19496@boulder.Colorado.EDU> baileyc@boulder.Colorado.EDU (BAILEY CHRISTOPHER R) writes: >I have an array, where only the end of it needs to be sorted (say the >last 5 elements). The part that confuses me the most is the comparand. The compare function is never affected by the number of elements to be compared: it operates pairwise. >So, say my array is mapping[10] and I need to sort all the elements >from mapping[4] to mapping [9]. How do I do this using qsort? The full ANSI C prototype for qsort is void qsort(void *base, size_t nmemb, size_t size, int (*compare)(void *, void *)); >So, I would assume that my base would be mapping[4], that num would be >10, and that width would be sizeof(int), but what about compare? No: the address of the first of the contiguous sequence of objects (`array') that you want sorted is `&mapping[4]', so `base' is (void *)&mapping[4] The number of elements to be sorted is 6 (namely mapping-sub-4, 5, 6, 7, 8, and 9), so `nmemb' is (size_t)6. The size of each element is sizeof(int). As for the compare function, you want one that returns less-than, equal-to, or greater-than zero depending on whether the integer at some location is less, equal, or greater than that at a second location. Qsort will pass only the location. Thus one proper comparison function is int mycompare(void *a, void *b) { return *(int *)a - *(int *)b; } >In my case, if mapping is [10], then the highest number that can be stored >in this array is 9, only the numbers 0 - 9 could be used in this array, and >each one only once. so mapping could look like: 1,3,5,9,8,2,7,6,0,4. Qsort does not know or care that the elements are unique, bounded, etc. All it wants is a contiguous sequence (`array') of objects of some fixed size, along with a pointer to a function that, given the address of two such objects, returns (consistently) a value <, ==, or > 0 depending on whether those two objects are `in order', `equal: order unimportant', or `out of order'. In your case, since you know much more about your numbers, you could come up with a more efficient sorting scheme. For six numbers, however, efficiency is not much of an issue. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@cs.umd.edu Path: uunet!mimsy!chris
john@chinet.chi.il.us (John Mundt) (04/15/90)
In article <19496@boulder.Colorado.EDU> baileyc@tramp.Colorado.EDU (BAILEY CHRISTOPHER R) writes: >I'm not sure how to use qsort. I have an array, where only the end of >it needs to be sorted (say the last 5 elements). The part that confuses >me the most is the comparand. So, say my array is mapping[10] and I need >to sort all the elements from mapping[4] to mapping [9]. How do I do this >using qsort? > intcmp(*one, *two) /* you provide the sorting function */ int *one, *two; /* which gets pointersw to two members */ { /* which qsort is comparing */ return(*one < *two); } some_function() { int mapping[10]; ... qsort((char *)&mapping[4], 6, sizeof(int *), intcmp); } >So, I would assume that my base would be mapping[4], Right, but the address of mapping[4], either as I show it above or mapping + 4 >that num would be 10, No, num is the number of items to be compared, mapping[4] to mapping[9], which is six items >and that width would be sizeof(int), No again. mapping is an int pointer, and we want to move one int pointer at a time. > but what about compare? .... >How do I use compare? All the examples I've seen the compare doesn't make >sense to me. the compare is simply a function that returns less than zero if the first item is less than the second, 0 if they are the same, or more than zero if the first item is greater than the second. Since you write the function, the decision as to what is greater or less is arbitrary. You can use standard library functions once removed too, so if you did a sort of strings passed to main, you could do int strcmp(); int strcmp2(s1, s2) char **s1, **s2; { return(strcmp(*s1, *s2)); } main(argc, argv) int argc; char **argv; { (void)qsort((char *) argv, argc, sizeof(char **), strcmp2); while (*argv) (void)printf("%s\n", *argv++); } -- --------------------- John Mundt Teachers' Aide, Inc. P.O. Box 1666 Highland Park, IL john@admctr.chi.il.us *OR* fred@teacha.chi.il.us (312) 998-5007 (Day voice) || -432-8860 (Answer Mach) && -432-5386 Modem
john@chinet.chi.il.us (John Mundt) (04/15/90)
In article <1990Apr14.220814.6261@chinet.chi.il.us> john@chinet.chi.il.us (John Mundt) writes: >In article <19496@boulder.Colorado.EDU> baileyc@tramp.Colorado.EDU (BAILEY CHRISTOPHER R) writes: > OF COURSE, I MEANT >intcmp(*one, *two) /* you provide the sorting function */ >int *one, *two; /* which gets pointersw to two members */ >{ /* which qsort is comparing */ > return(*one - *two); ^ >} -- --------------------- John Mundt Teachers' Aide, Inc. P.O. Box 1666 Highland Park, IL john@admctr.chi.il.us *OR* fred@teacha.chi.il.us (312) 998-5007 (Day voice) || -432-8860 (Answer Mach) && -432-5386 Modem