[comp.lang.c] qsort - part of an array

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