[comp.lang.c] HOW does "qsort" handle different variable type?

rcoahk@chudich.co.rmit.oz (Alvaro Hui Kau) (03/23/91)

Hi,

	I am interested in HOW the system routine
	handle different variable types..

	Furthermore, WHY char casting is used for
	the base pointer?

	Thanks.
alvaro,

===============================================================================
	Alvaro Hui		|ACSnet		akkh@mullian.oz
    5th Year B.E.\ B.Sc.	|Internet &	akkh@mullian.ee.mu.OZ.AU
   University of Melbourne	|Arpanet	rcoahk@koel.co.rmit.OZ.AU 

stan@Dixie.Com (Stan Brown) (03/24/91)

rcoahk@chudich.co.rmit.oz (Alvaro Hui Kau) writes:

>Hi,

=>	I am interested in HOW the system routine
=>	handle different variable types..
=
=>	Furthermore, WHY char casting is used for
=>	the base pointer?
=
=>	Thanks.
=>alvaro,

	qsort(0 only implements the *sort* alogrithim.  It depends upon calls
	to a user suplied routine (strcmp for example) which can compare two
	objects of the type to be sorted and return the results of the comparison
	to it.

	I would referr you to an excelent article on the subjetc in C users 
	magizine about sxi months ago.  If you can't find it mail me & I will
	look up the issue for you.



-- 
Stan Brown	P. c. Design 	404-363-2303	Ataant Ga.
(emory|gatech|uunet) rsiatl!sdba!stan				"vi forever"

bhoughto@nevin.intel.com (Blair P. Houghton) (03/24/91)

In article <1991Mar23.063112.22168@minyos.xx.rmit.oz.au> rcoahk@chudich.co.rmit.oz (Alvaro Hui Kau) writes:
>Hi,
>	Furthermore, WHY char casting is used for
>	the base pointer?

Even in ANSI C, you can expect a pointer to char to be a pointer
to a byte.  This makes it a natural choice for a generic pointer
type.  It means that when the pointer is incremented by 1, the
location it points to will be one byte further in the memory.

Notice that you have to give also the number of bytes that
each object occupies.  qsort() uses that number to increment
the pointer and thus point to the next object, not just
the next byte.

In ANSI C, however, there's a special type, `void *', which
is designed specifically to be a generic pointer type, to
be used in exactly this way.

qsort()'s sorting algorithm often isn't the best [*] (the
algorithm you use should depend on the distribution and
organization of your data, so it's easy to define a class
of sets that make a given sorting algorithm thrash and
slog), but this usage of anonymous data methods is a
classic of modular programming.

				--Blair
				  "Waxing didactic this week..."

[*] the algorithm it uses can be different from library
to library:  anything from bubble-sort to hashing.

gwyn@smoke.brl.mil (Doug Gwyn) (03/25/91)

In article <1991Mar23.063112.22168@minyos.xx.rmit.oz.au> rcoahk@chudich.co.rmit.oz (Alvaro Hui Kau) writes:
>	I am interested in HOW the system routine
>	handle different variable types..
>	Furthermore, WHY char casting is used for
>	the base pointer?

I think your question boils down to, "Explain the function of the first
argument to the qsort() function."

qsort()'s first argument is a "generic" pointer, formerly of type char*,
in ANSI C of type void*.  The reason for this is of course that the
implementation of qsort() has no way of knowing what the actual data
type will be at run time.  The third argument to qsort() specifies the
byte-width of a single element in the array of whatever actual type is
being sorted, so that qsort() is able to construct generic pointers to
the proper elements that it passes to the user-supplied comparison
function.  qsort() manages the sorting algorithm, while the user-
supplied comparison function gives meaning to comparison of whatever
data types are actually being sorted.  Note that the comparison function
has generic-pointer types for its arguments, which must be converted to
pointers to the actual data types being compared.