chris@mimsy.UUCP (Chris Torek) (09/21/89)
In article <5217@merlin.usc.edu> jeenglis@nunki.usc.edu (Joe English) writes: >As long as we're on the subject of sorting, I was >wondering why the standard sort routine is implemented >as a quick-sort nearly everywhere, given its poor >worst-case behaviour. Any guesses? If true: laziness. If not: well, no answering `why' for a question that is false. (qsort simply means `apply some reasonably fast sort', not `apply quicksort'. There is no reason someone could not put in all sorts of sorts, selected automatically at runtime, perhaps.) It is worth noting that 4.3BSD uses a modified quick sort that (a) chooses one of three for its partition element and (b) switches to an insertion sort when the number of items in a partition is `small' (<= 10). It also does the larger partition using tail recursion (i.e., `goto') so that the stack does not get as deep. The `median of three' keeps qsort from being worst-case on nearly sorted arrays. The insertion sort should be obvious. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
lhf@aries5 (Luiz H de Figueiredo) (11/19/89)
In a recent thread about sorting strings, someone suggested that qsort was not the way to go because quicksort is not very good for nearly ordered files. My question is: Does qsort have to implement quicksort? My point is that the *name* qsort is historical but qsort can actually be very smart, eg. switching to insertion for small segments and/or pre-scan the file (array) to avoid quadratic behaviour for sorted data. In other words, qsort does not even have to implement quicksort at all! What is more useful to assume is that qsort is *very* efficient, so that we don't have to re-invent the wheel every day. What does the standard say about this? Luiz Henrique de Figueiredo internet: lhf@aries5.uwaterloo.ca Computer Systems Group bitnet: lhf@watcsg.bitnet University of Waterloo Waterloo, Ontario, Canada N2L 3G1
gwyn@smoke.BRL.MIL (Doug Gwyn) (11/19/89)
In article <860@maytag.waterloo.edu> lhf@aries5 (Luiz H de Figueiredo) writes: > Does qsort have to implement quicksort? No. The interesting question is whether the sort is required to be "stable", and the answer to that is also "no".
ok@mudla.cs.mu.OZ.AU (Richard O'Keefe) (11/19/89)
In article <860@maytag.waterloo.edu>, lhf@aries5 (Luiz H de Figueiredo) writes: > In a recent thread about sorting strings, someone suggested that qsort was > not the way to go because quicksort is not very good for nearly ordered files. > My question is: > Does qsort have to implement quicksort? The standard will let an implementor code qsort() any way he likes. It's worth checking your manual to find out what you actually have. My manual says qsort() is an implementation of the quicker-sort algorithm. which is what the UNIX manual has said since V7. I've come across one PC version which used Shell sort. > What is more useful to assume is that qsort is *very* efficient, so that we > don't have to re-invent the wheel every day. It is not useful to assume that qsort is *very* efficient, because whenever I have tested it I have found that it *isn't*. On UNIX systems, my merge- sort typically runs about 30% faster than qsort(), and I _know_ my code can be improved. What *IS* useful is to assume that qsort() is THERE. In most programs even the cost of qsort() is a small fraction of the total cost of the program. So what you do is write your program using qsort() -- because it is there -- and then profile it -- because it isn't very fast -- and IF the sort turns out to be taking a lot of time, FIRST you try very hard to make your comparison function fast, and THEN if a 30% improvement is going to help you look at replacing qsort(). If you have a complicated comparison function, a good trick is to make a pass over the array generating a new key which is easier to compare. For example, if you want to sort "MM/DD/YY stuff" it is worth recoding it as "YYmdstuff" where m and d are single characters, and then you can use one strcmp() instead of more complicated code.
gaynor@busboys.rutgers.edu (Silver) (11/19/89)
Those looking for the source to a good quicksort, try consulting your GNU Emacs distribution. .../etc/qsort.c contains a fairly well documented, pretty fast quicksort. (If intuition serves me, it's a well-tuned bruiser of quicksort.) The code falls under the same General Public License as the rest of the FSF software. Regards, [Ag]
ejp@bohra.cpg.oz (Esmond Pitt) (11/20/89)
In article <860@maytag.waterloo.edu> lhf@aries5 (Luiz H de Figueiredo) writes: >In a recent thread about sorting strings ... Aha! I have been looking for the newsgroup this happended in. Could somebody possibly send me copies of the discussion, specifically the items about the revised heapsort. I somehow lost my copies. Tks. -- Esmond Pitt, Computer Power Group ejp@bohra.cpg.oz
lee@sq.sq.com (Liam R. E. Quin) (11/24/89)
In article <860@maytag.waterloo.edu> lhf@aries5 (Luiz H de Figueiredo) writes: > My question is: > Does qsort have to implement quicksort? Well, it would certainly be helpful if it did! Otherwise how would even begin to guess the complexity of one's programs? > My point is that the *name* qsort is historical but qsort can actually be > very smart, eg. switching to insertion for small segments and/or pre-scan the > file (array) to avoid quadratic behaviour for sorted data. Prescanning the array adds O(n) to the sort, slowing it down unacceptably. It also adds disastrous paging behaviour for large arrays! It is too late for insertaion sort, since the array is sorted in place, and is already filled by the time qsort is called. But 4.3BSD qsort() does in fact switch to a different algorithm for short arrays, reducing the depth of recursion slightly. There is also some minimal effort at avoiding the worst-case behaviour, as I recall. That qsort() routine is on the tape of publicly available files from the 4.3 Tahoe release. THe point is (I think) that it is *at least* as fast as QuickSort, so you don't need to worry about that aspect. The improved worst-case and typical-case behaviour is a further incentive to use it as far as I am concerned, although I don't know if the same changes have mede it into System V. > What is more useful to assume is that qsort is *very* efficient, so that we > don't have to re-invent the wheel every day. As I said in mail to soneone else today, if you save an average of one whole second in runtime of the sort routine, at the cost of one hour's programming, it takes 3,600 runs of the program before you even start to break even. And the extra cost of maintaining and debugggging your code may make it worse. If you save a millisecond, it takes 3,600,000 calls to LuizSort() before you start to win. And if your routine has to be ported.... But if you can save an hour, then do it. First make it work, then make it fast. [Brian Kernighan? from ``Elements of Programming Style''? Sorry, I forget which Bible I am quoting!] So I agree strongly -- use qsort. Sorry to bring this up on comp.lang.c -- there seem to have been a lot of "how do I sort" questions of late, though, so I thought it might be worth while repeating. Lee -- Liam R. Quin, Unixsys (UK) Ltd [note: not an employee of "sq" - a visitor!] lee@sq.com (Whilst visiting Canada from England) People caught shopping are warned that they will be fined by an amount not exceeding the total value of their purchases, plus sales tax.
root@ozdaltx.UUCP (root) (02/12/90)
After going over the manuals more times than I'd like, I still can't
figure out how to get qsort() (S) to operate. The example shows
something like:
void qsort(base, nel, width, compar)
char *base
unsigned nel, width
int (*compar)()
Is base supposed to be an array?
nel & width are self-explanitory
What is compar() looking for or how is it assigned?
The objective is to sort an array of strings in alpha order and then
be able to read them. So far I'm getting is core dumps.
Any help, suggestions will be appreciated.
thanks
Scotty
------
AIDS INFORMATION EXCHANGE BBS (214) 247-2367/247-5609
"Education is the best weapon"
{ames,rutgers,texsun,smu}!attctc!ozdaltx!sysop vp@fctunl.rccn.pt (Vasco Pedro) (02/13/90)
In article <5916@ozdaltx.UUCP> root@ozdaltx.UUCP (root) writes: > > void qsort(base, nel, width, compar) > char *base > unsigned nel, width > int (*compar)() > > Is base supposed to be an array? > nel & width are self-explanitory > What is compar() looking for or how is it assigned? > Yep, 'base' is supposed to the be the (char *)base of the array you intend to sort. 'nel' is the number of elements to be sorted and 'width' the sizeof(element_to_sort). 'compar' is a pointer to int function that must behave like strcmp(s1,s2) a that will be called by qsort(...), for each two elements that will be compared, ie, if elements 2 and 4 need be compared there will be a call of the form: compar(base+(2-1)*width, base+(4-1)*width). If is strings you want to sort might just call (I think): qsort(array,nel,width,strcmp). Sorry for the inaccuracies and hope this helps. -- --- Vasco Pedro BITNET/Internet: vp@host.fctunl.rccn.pt Phone: (+351) (1) 295-4464 (1360) ARPA: vp%hara.fctunl.rccn.pt@mitvma.mit.edu Fax: (+351) (1) 295-4461 PSI/VMS: PSI%(+2680)05010310::HOST::vp UUCP: ...mcvax!inesc!unl!vp Snail: Dept. de Informatica, Universidade Nova de Lisboa 2825 Monte Caparica, PORTUGAL
jha@spodv5.UUCP (Johan Harsta) (02/13/90)
In article <5916@ozdaltx.UUCP>, root@ozdaltx.UUCP (root) writes: > After going over the manuals more times than I'd like, I still can't > figure out how to get qsort() (S) to operate. The example shows > something like: > > void qsort(base, nel, width, compar) > char *base > unsigned nel, width > int (*compar)() > > Is base supposed to be an array? - 'base' should be a pointer to the base of the table, and of type pointer to an element in the table, casted to a pointer to character > nel & width are self-explanitory > What is compar() looking for or how is it assigned? - 'compar' is supplied by you; e.g. 'strcmp' or a modified version of it E.g.: struct ELEMENT buffer[nele]; sort_buf (&buffer[0], nele); void sort_buffer (base, nele) struct ELEMENT *base; int nele; { qsort ((char *) base, (unsigned) nele, (unsigned) sizeof (struct ELEMENT), sorting_alg); return; } int sorting_alg (arg1, arg2) char *arg1; char *arg2; { return (strncmp (arg1, arg2, MAX_RELEVANT_CHARACTERS)); } Something like the above should work, good luck! /Johan Harsta, Programator Uppsala AB, Sweden (consultant for Philips)
gegu@bii.UUCP (Gerhard Gucher) (02/13/90)
In article <5916@ozdaltx.UUCP>, root@ozdaltx.UUCP (root) writes: > After going over the manuals more times than I'd like, I still can't > figure out how to get qsort() (S) to operate. The example shows > something like: > > void qsort(base, nel, width, compar) > char *base > unsigned nel, width > int (*compar)() > > Is base supposed to be an array? > nel & width are self-explanitory > What is compar() looking for or how is it assigned? > > > The objective is to sort an array of strings in alpha order and then > be able to read them. So far I'm getting is core dumps. > qsort is a little bit tricky for arrays of strings. compar() will get the address of two items to be sorted as arguments. Since your arguments are strings (char*'s) you must supply a compare function which accepts (char**)'s as args. The Example has been tested on a SUN OS 4.03 cc compiler. Example: #define NUM_ELEM(a) ( sizeof(a)/sizeof(a[0]) ) /* array to be sorted */ char * array[] = { "beta", "gamma", "alpha", "delta", "epsilon" }; extern int qsort(); /****************************************************************/ int ind_strcmp(s,t) /* indirect string compare for qsort */ char** s; char** t; { return( strcmp(*s,*t) ); } /****************************************************************/ /* ARGSUSED */ int main(argc,argv) int argc; char *argv[]; { int i; (void) qsort( (char*)(&array[0]), NUM_ELEM(array), sizeof(array[0]), ind_strcmp /* gets the address of the char ptrs */ ); /* print the sorted array */ for( i=0; i< NUM_ELEM(array); i++ ) (void)printf( "%s\n", array[i] ); } /* main() */ -- +------------------------------------------------------------------+ | Gerry Gucher uunet!bii!gegu gegu@bii.bruker.com | | Bruker Instruments Inc. Manning Park Billerica MA 01821 | +------------------------------------------------------------------+
ryan@sjuphil.uucp (Patrick M. Ryan) (02/14/90)
In article <5916@ozdaltx.UUCP> root@ozdaltx.UUCP (root) writes: >After going over the manuals more times than I'd like, I still can't >figure out how to get qsort() (S) to operate. The example shows >something like: > > void qsort(base, nel, width, compar) > char *base > unsigned nel, width > int (*compar)() > >Is base supposed to be an array? >nel & width are self-explanitory >What is compar() looking for or how is it assigned? > >The objective is to sort an array of strings in alpha order and then >be able to read them. So far I'm getting is core dumps. yes, base is supposed to be an array. compar() takes two pointers to structures to compare. compare must return an integer (say, ret) to indicate the order of the two items. ret = 0 if they are equal, ret < 0 if the first item is less than the second, and ret > 1 other wise. ex: #define LEN 32 #define MAX 512 char str[LEN][MAX]; int compare(); main() { . . . qsort(str,MAX,LEN,compare); . . } int compare(s1,s2) char *s1, *s2; { return(strcmp(s1,s2)); } -- patrick m. ryan ryan%sjuphil.sju.edu@bpa.bell-atl.com {bpa|burdvax|princeton|rutgers}!sjuphil!ryan pmr@gemini.gsfc.nasa.gov
root@ozdaltx.UUCP (root) (02/14/90)
Just want to say THANKS TO ALL the many responces I received about
qsort(). I know I can always count on the net.gurus to clairify or
help with a problem. It is fustrating when the manuals are poorly
written without decent examples, seems as if one almost has to know
how something works before reading up on it. Too much is assumed by
the manual writters.
I'll post a summery of responces in the next day or so, maybe someone
else will bebefit for it.
Scotty
------
AIDS INFORMATION EXCHANGE BBS (214) 247-2367/247-5609
"Education is the best weapon"
{ames,rutgers,texsun,smu}!attctc!ozdaltx!sysop daved@physiol.su.oz (Dave Davey) (02/15/90)
jha@spodv5.UUCP (Johan Harsta) writes: |In article <5916@ozdaltx.UUCP>, root@ozdaltx.UUCP (root) writes: |> After going over the manuals more times than I'd like, I still can't |> figure out how to get qsort() (S) to operate. The example shows |E.g.: | struct ELEMENT buffer[nele]; | sort_buf (&buffer[0], nele); | void | sort_buffer (base, nele) | struct ELEMENT *base; | int nele; | { /*****************************/ int sorting_alg(); /**** needs this declaration */ /*****************************/ | qsort ((char *) base, | (unsigned) nele, | (unsigned) sizeof (struct ELEMENT), | sorting_alg); | return; | }
msb@sq.sq.com (Mark Brader) (02/21/90)
> > void qsort(base, nel, width, compar) > > char *base > > unsigned nel, width > > int (*compar)() > Yep, 'base' is supposed to the be the (char *)base of the array you > intend to sort. 'nel' is the number of elements to be sorted and > 'width' the sizeof(element_to_sort). > 'compar' is a pointer to int function that must behave like strcmp... > If is strings you want to sort might just call (I think): > qsort(array,nel,width,strcmp). This is correct as far as it goes but there is a tricky point that must be emphasized. The compar function that you provide will be called with arguments that *point to* the elements of the array. (It works this way because the array elements might have a type that cannot be passed efficiently, or at all, as a function argument.) Therefore, if you have a 2-dimensional array of chars where each row is used to contain a string, like this: char place[][MAXLEN+1] = {"Portugal", "Canada", "Paraguay", "Japan"}; then you can indeed sort it with #define NUMEL(x) (sizeof x / sizeof *x) int strcmp(); qsort ((char *) place, NUMEL (place), sizeof *place, strcmp); However, if your array itself contains pointers, like this: char *place[] = {"Portugal", "Canada", "Paraguay", "Japan"}; then you must define a function int indstrcmp (sp1, sp2) char *sp1, *sp2; { return strcmp ( * (char **) sp1, * (char **) sp2); } The arguments to indstrcmp() have to be declared as char * rather than char **, and then converted to char **,, because char * is what qsort() is going to pass to indstrcmp(). and invoke qsort using it: qsort ((char *) place, NUMEL (place), sizeof *place, indstrcmp); All of the above is in pre-ANSI style. In ANSI C, void * rather than char * is used as the generic pointer type (but they're represented the same way and passed the same way to functions, so strcmp() will work on void *'s). So the first example becomes: qsort ((void *) place, NUMEL (place), sizeof *place, strcmp); and the second one: int indstrcmp (const void *sp1, const void *sp2) { return strcmp ( * (char **) sp1, * (char **) sp2); } and: qsort ((void *) place, NUMEL (place), sizeof *place, indstrcmp); Followups are directed to comp.lang.c. -- Mark Brader "[This computation] assumed that everything SoftQuad Inc., Toronto would work, a happy state of affairs found utzoo!sq!msb, msb@sq.com only in fiction." -- Tom Clancy This article is in the public domain.
daye@jacobs.cs.orst.edu (Garion) (01/17/91)
Could someone e-mail me the source for the qsort() function. I need to use it on a machine that lacks that function. Thanks! -- | Internet----- | 'I'll have to teach you a few of my spells. I | | daye@jacobs.cs.orst.edu | have one..a fireball..let's see, how did that | | daye@nyssa.cs.orst.edu | go..?' - If you don't know, you don't need to | My opinions are my own. I have opinions, therefore I am....
fangchin@portia.Stanford.EDU (Chin Fang) (01/19/91)
In article <1991Jan16.232816.3076@usenet@scion.CS.ORST.EDU> daye@jacobs.cs.orst.edu (Garion) writes: >Could someone e-mail me the source for the qsort() function. I need to use >it on a machine that lacks that function. Thanks! > >-- This kind of questions are getting popular in this group lately. They ought to go to comp.sources.wanted news group. Sources wanted -> comp.sources.wanted. As to the src, check p251. Numerical Recipes in C by P. H William et al. It is a very common book, should be availabel in any halfway decent research library. The lively discussions in this news group is quite enjoyable. Hope those want srcs go to the group more appropriate. I am not blaming such people, some simply don't know about comp.sources.wanted. As I recall, people want srcs typically have better luck there. Please don't turn a discussion group into an appendix of comp.sources.wanted. Regards, Chin Fang Mechanical Engineering Department Stanford University fangchin@portia.stanford.edu
garath@irie.ais.org (Belgarath) (04/15/91)
I am trying to learn how to use qsort(). If you can help please reply via e-mail, as I do not read this group regularly yet. I have a struct with 4 ints, a few chars, and a float. one is 'char name[15]' and the variable is defined as: struct the_struct people[49]; I want to use qsort() to sort the structure alphabetically according to the name field of the structure.. I don't quite understand the man page on qsort(). Can someone give me an example of how to do this please? Thank you.
garath@irie.ais.org (Belgarath) (04/22/91)
Thanks to everyone who mailed me with the solution to how to use
qsort(). Basically after you have defined the structure you do:
qsort((char *) info, 49, sizeof(the_srtuct), compare);
int compare(ptr1, ptr2)
struct the_struct *ptr1;
struct the_struct *ptr2;
{
return (strcmp(ptr1->name, ptr2->name));
}dkeisen@leland.Stanford.EDU (Dave Eisen) (04/22/91)
In article <1991Apr22.002627.14535@engin.umich.edu> garath@irie.ais.org (Belgarath) writes: > > Thanks to everyone who mailed me with the solution to how to use >qsort(). Basically after you have defined the structure you do: > >qsort((char *) info, 49, sizeof(the_srtuct), compare); > >int compare(ptr1, ptr2) >struct the_struct *ptr1; >struct the_struct *ptr2; >{ > return (strcmp(ptr1->name, ptr2->name)); >} Nope. The comparison function takes two "generic pointer" parameters, (void * in ANSI C, char * in Classic C), not parameters of some random type the implementor of qsort has never heard of. These parameters should then be cast to the appropriate type in your comparison function. Something like (since you seem to be using classic C): int compare (ptr1, ptr2) char *ptr1; char *ptr2; { return (strcmp (((struct the_struct *) ptr1)->name, ((struct the_struct *) ptr1)->name)); } -- Dave Eisen dkeisen@leland.Stanford.EDU 1101 San Antonio Raod, Suite 102 (Gang-of-Four is being taken off the net) Mountain View, CA 94043 (415) 967-5644
asd@cbnewsj.att.com (Adam S. Denton) (04/23/91)
In article <1991Apr22.002627.14535@engin.umich.edu> garath@irie.ais.org (Belgarath) writes: >qsort((char *) info, 49, sizeof(the_srtuct), compare); > >int compare(ptr1, ptr2) >struct the_struct *ptr1; >struct the_struct *ptr2; >{ > return (strcmp(ptr1->name, ptr2->name)); >} Not quite. This should really be int compare(ptr1,ptr2) char *ptr1, *ptr2; { return strcmp( ((struct the_struct *)ptr1)->name, ((struct the_struct *)ptr2)->name ); } and in an ANSI environment, "void *" should be used instead of "char *". qsort() passes generic pointers to compare(), not struct pointers. There is no guarantee the two pointer types are interchangeable. Adam Denton asd@mtqua.att.com
gwyn@smoke.brl.mil (Doug Gwyn) (04/23/91)
In article <1991Apr22.002627.14535@engin.umich.edu> garath@irie.ais.org (Belgarath) writes:
- Thanks to everyone who mailed me with the solution to how to use
-qsort(). Basically after you have defined the structure you do:
-
-qsort((char *) info, 49, sizeof(the_srtuct), compare);
-int compare(ptr1, ptr2)
-struct the_struct *ptr1;
-struct the_struct *ptr2;
-{
- return (strcmp(ptr1->name, ptr2->name));
-}
I don't know who mailed you that, but it is utterly wrong!jseymour@medar.com (James Seymour) (04/24/91)
In article <1991Apr22.174958.15420@cbnewsj.att.com> asd@cbnewsj.att.com (Adam S. Denton) writes: :In article <1991Apr22.002627.14535@engin.umich.edu> garath@irie.ais.org (Belgarath) writes: ::qsort((char *) info, 49, sizeof(the_srtuct), compare); :: ::int compare(ptr1, ptr2) ::struct the_struct *ptr1; ::struct the_struct *ptr2; ::{ :: return (strcmp(ptr1->name, ptr2->name)); ::} : :Not quite. This should really be : int compare(ptr1,ptr2) : char *ptr1, *ptr2; : { : return strcmp( ((struct the_struct *)ptr1)->name, : ((struct the_struct *)ptr2)->name ); : } :and in an ANSI environment, "void *" should be used instead of "char *". : :qsort() passes generic pointers to compare(), not struct pointers. :There is no guarantee the two pointer types are interchangeable. : :Adam Denton :asd@mtqua.att.com Mea culpa! As Adam (and in another article, Dave Eisen) correctly pointed out, the function called by qsort() *should* have it's parms declared as char*/void*. Being one of those that mailed qsort pointers (no pun intended) to Belgarath, I thought it only fair to own up to my snafu. -- Jim Seymour | Medar, Inc. ...!uunet!medar!jseymour | 38700 Grand River Ave. jseymour@medar.com | Farmington Hills, MI. 48331 CIS: 72730,1166 GEnie: jseymour | FAX: (313)477-8897
wolfram@cip-s08.informatik.rwth-aachen.de (Wolfram Roesler) (04/24/91)
garath@irie.ais.org (Belgarath) writes: >qsort((char *) info, 49, sizeof(the_srtuct), compare); >int compare(ptr1, ptr2) >struct the_struct *ptr1; >struct the_struct *ptr2; >{ > return (strcmp(ptr1->name, ptr2->name)); >} The problem is that this will probably work on some - many - machines. It will certainly work on PC, ST and some Unix systems. Well, the problem in fact is that it will not work on some other systems. Use it only if you are absolutely sure you will never port the program to a different system or compiler (you are NEVER sure you will never do this, however). It just isnt portable.