qsort() effective? efficient?
I1269U
seen it anywhere else before which makes me wonder if it's a standardized
function. Regardless of the fact of whether it's a standard function or not,
I'd like to know how efficient and/or effective it is. I used it to sort an
array of structures based on one field (namely a name string in the structure)
and it seemed to work well, especially since I can write the basic selection
algorithm without having to write the entire sorting algorithm. In case you
have no idea what I'm talking about, the function itself works like this (at
least this is what I've been told):
The prototype:
void qsort(void *base, size_t num, size_t size, int (*cmp)(void *element1,
void *element2));
Where : void *base is a pointer to the first element in the array that is to
be sorted. It's void so that it can work with any data type.
size_t num is the number of elements in the array that is to be sorted.
size_t size is the size of each individual element in the array.
int (*cmp)(void *element1, void *element2) is a pointer to either a function
defined in a header, or a user defined function. The function itself is meant
to compare the two elements (element1 and element2), and return 1 of 3
possible values (well...you can return any int value, but it determines it's
action in only three ways).
return < 0 means element 1 is less than element 2
return of 0 means they are equal
return > 0 means element 1 is greater than element 2
In the first two cases it leaves them as they are. In the last case (return >
0) it switches the two elements in the array, so that the smaller one now
comes before the larger value.
Of course, you could define the function to return the opposite of this so as
to sort into descending order instead of the default ascending order.
So has anyone heard of this function? If so, is it a function that should be
used, or should it be avoided due to inefficient code?
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Richard Heathfield
>I found a function called qsort() in a book of mine the other day. I had
never
>seen it anywhere else before which makes me wonder if it's a standardized
>function. Regardless of the fact of whether it's a standard function or
not,
>I'd like to know how efficient and/or effective it is. I used it to sort an
>array of structures based on one field (namely a name string in the
structure)
>and it seemed to work well, especially since I can write the basic
selection
>algorithm without having to write the entire sorting algorithm.
<snip qsort man page!>
>So has anyone heard of this function? If so, is it a function that should
be
>used, or should it be avoided due to inefficient code?
qsort is indeed an ANSI standard function (although it doesn't necessarily
implement the quicksort algorithm - but it must sort somehow if used
correctly - and I believe most implementations use the quicksort algorithm).
As for efficiency, it depends who you listen to. If you want to squeeze the
last four nanoseconds of flab out of your code, you /might/ be able to write
(or more likely, 'borrow') faster code. Some people /really/ don't like
qsort, IIRC.
But I use it quite a lot. I suggest you do the same, if you so desire.
Regards
---
Richard H
#include "sig.h"
Jack Klein
wrote:
> I found a function called qsort() in a book of mine the other day. I had never
> seen it anywhere else before which makes me wonder if it's a standardized
> function. Regardless of the fact of whether it's a standard function or not,
> I'd like to know how efficient and/or effective it is. I used it to sort an
> array of structures based on one field (namely a name string in the structure)
> and it seemed to work well, especially since I can write the basic selection
> algorithm without having to write the entire sorting algorithm. In case you
> have no idea what I'm talking about, the function itself works like this (at
> least this is what I've been told):
>
> The prototype:
>
> void qsort(void *base, size_t num, size_t size, int (*cmp)(void *element1,
> void *element2));
>
> Where : void *base is a pointer to the first element in the array that is to
> be sorted. It's void so that it can work with any data type.
>
> size_t num is the number of elements in the array that is to be sorted.
>
> size_t size is the size of each individual element in the array.
>
> int (*cmp)(void *element1, void *element2) is a pointer to either a function
> defined in a header, or a user defined function. The function itself is meant
> to compare the two elements (element1 and element2), and return 1 of 3
> possible values (well...you can return any int value, but it determines it's
> action in only three ways).
>
> return < 0 means element 1 is less than element 2
> return of 0 means they are equal
> return > 0 means element 1 is greater than element 2
>
> In the first two cases it leaves them as they are. In the last case (return >
> 0) it switches the two elements in the array, so that the smaller one now
> comes before the larger value.
>
> Of course, you could define the function to return the opposite of this so as
> to sort into descending order instead of the default ascending order.
>
> So has anyone heard of this function? If so, is it a function that should be
> used, or should it be avoided due to inefficient code?
<Jack>
Don't you have a reference manual, compiler manual, online help, or
man pages in which you can look up a function to see whether or not it
is part of the standard library? If not, get one quickly.
qsort() is a 100% ANSI/ISO standard function prototyped in <stdlib.h>.
The standard does not impose any requirements on the algorithm used of
its efficiency, that is a quality of implementation issue. In
general, however, most implementations of qsort() are pretty good.
It is always possible to write a specific sorting function if you know
what the unsorted order of the data set will look like that will run
faster than a generic function like qsort(). Sorting algorithms are a
complex topic in themselves, and not particularly C related.
Even so, unless you are writing a program which spends large amounts
of time sorting large amounts of records, the qsort() which comes with
your compiler is almost certainly more than adequate for the
occasional sorting needs of most programs.
</Jack>
--
Do not email me with questions about programming.
Post them to the appropriate newsgroup.
Followups to my posts are welcome.
Lawrence Kirby
i12...@my-dejanews.com "I1269U" writes:
>I found a function called qsort() in a book of mine the other day. I had never
>seen it anywhere else before which makes me wonder if it's a standardized
>function.
Yes, qsort() is part of the standard C library.
>Regardless of the fact of whether it's a standard function or not,
>I'd like to know how efficient and/or effective it is.
Impossible to say. It is as efficient (or inefficient) as the person who wrote
the particular implementation of it you are using decided to make it. All
the standard specifies is that it sorts, it doesn't specify what sorting
algorithm should be used. The standard never makes any statements about
efficiency.
>I used it to sort an
>array of structures based on one field (namely a name string in the structure)
>and it seemed to work well, especially since I can write the basic selection
>algorithm without having to write the entire sorting algorithm. In case you
>have no idea what I'm talking about, the function itself works like this (at
>least this is what I've been told):
qsort() is usually reasonably efficient. If you tried it and its speed
is adequate there's no great reason not to use it
>The prototype:
>
>void qsort(void *base, size_t num, size_t size, int (*cmp)(void *element1,
>void *element2));
Those should be const void *element1 and const void *element2.
...
>So has anyone heard of this function? If so, is it a function that should be
>used, or should it be avoided due to inefficient code?
It is a function I have used on various occasions. The main pitfall is to
make sure you define the comparison fucntion correctly. It must be of the
form
int function_name(const void *arg1, const void *arg2)
{
...
}
Within the function body you can convert arg1 and arg2 to the appropriate
pointer types.
--
-----------------------------------------
Lawrence Kirby | fr...@genesis.demon.co.uk
Wilts, England | 7073...@compuserve.com
-----------------------------------------
Zoub-Zoub
As for the speed, if it uses the real Quicksort algorithm, it should be pretty efficient. On the average, it is the best sorting function.
But if you want to convince yourself, get a copy of a book on data structures and algorithms (such as Data structures and algorithms in C++, which is excellent even though it is in C++, or The art of Computer Programming: Volume 3: sorting and searching, by Donald E. Knuth (the master...), which is a reference but hard to read, or any other) and implement the sorting algorithms. You'll see how fast Quicksort is.
So if the function is well implemented by your compiler, use it. It's handy and fast.
Zoub-Zoub
Zoub-Zoub
Zoub-Zoub
As for the speed, if it uses the real Quicksort algorithm, it should be pretty efficient. On the average, it is the best sorting function.
I1269U
>Don't you have a reference manual, compiler manual, online help, or
>man pages in which you can look up a function to see whether or not it
>is part of the standard library? If not, get one quickly.
Is there a particular book that you could suggest? I have about three
books. One is a beginners book I bought a couple months ago which
doesn't really go into any detail about the ANSI standard libraries,
except those functions which are most common (like scanf() and stuff).
Another is also a beginners text book which again doesn't go into
detail about the ANSI standard. The last one is an advanced book which
my dad tried to use once (even though I doesn't know the first thing
about C) and which doesn't go into detail about the ANSI standard
libraries because it assumes that anyone reading such an advanced book
already knows the standard libraries.
Zoub-Zoub
Richard Heathfield
<36e5be55...@news.intermediatn.net>...
a) K&R2. Or, to expand, "The C Programming Language", 2nd edition, Brian W
Kernighan and Dennis M Ritchie. These guys wrote the language. What they
say is pretty much as authoritative as the ANSI C Standard itself (although
in the rare cases where they conflict, the standard takes priority. I doubt
if you will find such clashes to be an issue in your own programming).
b) Both MSVC(++) and Borland C(++) have compatibility help on all
functions. Type qsort, press F1, look at the resulting help page. If you
are using some other compiler, try the man pages (if it's Linux) or other
on-line docs. If that doesn't work, revert to the book. See a).
--
Richard H
#include "sig.h"
Richard Heathfield
invisible. In my newsreader, I only get the text if I go to the trouble of
replying to it!
--
Richard H
#include "sig.h"
Zoub-Zoub <ppro...@ken.univ-mlv.fr> wrote in article
<36E625E2...@ken.univ-mlv.fr>...
> Same as the other replys.
> As for the speed, if it uses the real Quicksort algorithm, it should be
pretty
> efficient. On the average, it is the best sorting function.
> But if you want to convince yourself, get a copy of a book on data
structures and
> algorithms (such as Data structures and algorithms in C++, which is
excellent
> even though it is in C++, or The art of Computer Programming: Volume 3:
sorting
> and searching, by Donald E. Knuth (the master...), which is a reference
Stephan Wilms
>
> On 9 Mar 1999 15:29:15 GMT, jack...@att.net (Jack Klein) wrote:
>
> >Don't you have a reference manual, compiler manual, online help, or
> >man pages in which you can look up a function to see whether or not it
> >is part of the standard library? If not, get one quickly.
>
> Is there a particular book that you could suggest?
A good and well written introductory book to C is:
C Programming: A Modern Approach.
K.N.King.
W.W.Norton & Company, 1996.
ISBN 0-393-96945-2
An if you're interested in an online reference for C have a look
at the online version of the excellent book "Standard C - A Reference"
by P.J. Plauger:
http://www.dinkumware.com/htm_cl/index.html
Stephan
(initiator of the campaign against grumpiness in c.l.c)
(-: A brandnew excellent FAQ version has been released !!! :-)
(-: Get it: http://www.eskimo.com/~scs/C-faq/versions.html :-)
Cameron Foster
>On 9 Mar 1999 15:29:15 GMT, jack...@att.net (Jack Klein) wrote:
>
>>Don't you have a reference manual, compiler manual, online help, or
>>man pages in which you can look up a function to see whether or not it
>>is part of the standard library? If not, get one quickly.
>
>
>Is there a particular book that you could suggest? I have about three
>books. One is a beginners book I bought a couple months ago which
>doesn't really go into any detail about the ANSI standard libraries,
>except those functions which are most common (like scanf() and stuff).
>Another is also a beginners text book which again doesn't go into
>detail about the ANSI standard. The last one is an advanced book which
>my dad tried to use once (even though I doesn't know the first thing
>about C) and which doesn't go into detail about the ANSI standard
>libraries because it assumes that anyone reading such an advanced book
>already knows the standard libraries.
An excellent reference (not tutorial) book which is highly recommended
here is:
C - A Reference Manual (4th edition)
by Samuel P. Harbison and Guy L. Steele
Published by Prentice-Hall
ISBN 0-13-326224-3 (paperback)
commonly referred to as H&S.
--
Cameron Foster
http://www.fosterreaves.com
cdfo...@ix.netcom.com
http://www2.netcom.com/~cdfoster/
Will Rose
: On 9 Mar 1999 15:29:15 GMT, jack...@att.net (Jack Klein) wrote:
: >Don't you have a reference manual, compiler manual, online help, or
: >man pages in which you can look up a function to see whether or not it
: >is part of the standard library? If not, get one quickly.
: Is there a particular book that you could suggest? I have about three
: books. One is a beginners book I bought a couple months ago which
: doesn't really go into any detail about the ANSI standard libraries,
: except those functions which are most common (like scanf() and stuff).
: Another is also a beginners text book which again doesn't go into
: detail about the ANSI standard. The last one is an advanced book which
: my dad tried to use once (even though I doesn't know the first thing
: about C) and which doesn't go into detail about the ANSI standard
: libraries because it assumes that anyone reading such an advanced book
: already knows the standard libraries.
The usual recommmendation for a _reference_ book is Harbison and Steele,
C, A Reference Manual, now on its fourth edition.