A
Albert
What is the time complexity of qsort from the standard library? Please
provide a reference.
provide a reference.
C
Chris M. Thomasson
B
Ben Pfaff
Albert said:
The standard doesn't say.
International ISO/IEC standard 9899, second edition, 1999-12-01.
A
Albert
Debanjan said:
That *cannot* be right. pg 34 of 'The Practice of Programming' says
"the runtime [of "just about the simplest implementation"] can grow
more like n^2".
If qsort is O(n^2), I could not have scored 100% for my solution to
Space Invaders (from the Australian Invitational Informatics Olympiad
2009) - I was presented with 10^5 motherships and I chose to sort them
by x-coordinate using qsort. The square of 10^5 is 10^10 - a computer
can only do 10^8 operations a second, meaning that my solution would
have time out'ed in a few of the final test cases and I would _not_
have scored 100%. The time complexity of qsort from the standard
library is _not_ the same as the one I see in material that discusses
data structures.
Actually, I'm unlikely to need the time complexity of qsort in the
standard library - just for gcc, as that is the one used on the
Australian Informatics Training site and the International Olympiad of
Informatics.
K
Keith Thompson
Debanjan said:
You're thinking of Quicksort. The standard doesn't specify what
algorithm qsort uses. The name "qsort" was almost certainly
inspired by the name "Quicksort", and I strongly suspect that
the first implementation, before it was standardized, did use the
Quicksort algorithm, but there are no guarantees.
A conforming C implementation could even use bubblesort or bogosort
for qsort() -- though it would be a very silly thing to do.
(It's probably safe to assume that most or all implementations use
some O(N log N) sorting algorithm.)
B
BGB / cr88192
Albert said:
theoretically, it is whatever the hell the implementation wants it to be...
in practice, it is most likely to be O(n log2 n)
S
Seebs
Whatever the implementor wants it to be.
The reference is, of course, the requirements imposed by the standard on
the time complexity of qsort: Specifically, no paragraph, on no page,
of the standard. In total, it says: ""
As you can see, there is a bit of leeway for implementation preference
here.
-s
G
Gene
If qsort() is implemented with the quicksort algorithm, then the worst
case performance is O(n^2), but unless the initial ordering is
pathalogically bad, it's O(n log n). Moreover, the exact number of
comparisons is less than other O(n log n) sorting algorithms in the
average case. Finally, quicksort with introspection can avoid the
worst case performance by switching to a known worst case O(n log n)
algorithm when it looks like the quicksort is going badly.
B
Beej Jorgensen
Seebs said:
In the future, qsort() will be Quantum Sort, O(1)! Yay!
-Beej
N
Noob
Albert said:
The standard does not specify any specific sorting algorithm.
gcc does not provide qsort, glibc does.
http://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/qsort.c
The libc-help mailing list is the place to discuss glibc.
http://sourceware.org/ml/libc-help/
Regards.
S
Seebs
Or BSD libc. Or uclibc. Or klibc. Or newlib.
(Picked those examples because I've built all four with gcc.)
-s
N
Nobody
Quicksort (which may or may not be the algorithm used by the qsort()
function) is O(n^2) in the worst case, O(n.log(n)) in the typical case.
Quicksort requires choosing a pivot value to partition each sub-list. If
the partitioning is consistently uneven, the binary tree degenerates to a
linked list, i.e. the depth is O(n) rather than O(log(n)), resulting in
O(n^2) behaviour.
However, as the input gets larger, the probability of repeatedly choosing
bad pivots (and thus getting O(n^2) behaviour) decreases.
For any given input size n, there are n! possible orderings. Among these
orderings, the statistical distribution of run-times has a mean, median
and mode which are O(n.log(n)), but also has a long tail which doesn't
reach zero until O(n^2).
Improving the pivot selection (e.g. the median of three random values
rather than a single random value) will cause the tail to fall off
faster. You still get O(n^2) worst-case behaviour, but it becomes even
less likely.
R
Richard Tobin
Albert said:
Ken Thompson supposedly said that if he were designing the Unix system
again, he'd spell "creat" with an "e" on the end. A better change
would be to spell "qsort" "sort". That it originally used quicksort
is just an implementation detail which should not have been reflected
in the name of the function.
-- Richard
U
user923005
Many library implementations are now introspective sort.
Of course, the standard library implementors are free to choose any
algorithm that they like.
His original question is equivalent to:
How fast is a fast animal?
Please prove your answer.
A
Albert
user923005 said:
Not quite. I was hoping for something like:
"I've never seen a compiler provide an O(n^2) qsort", listing a few
references to compiler documentations, so qsort is probably O(nlogn)
S
Seebs
I'm pretty sure I've seen at least one compiler which provides unmodified
original quicksort, which is O(n^2) in bad cases. At this point, I wouldn't
own any hardware on which the operating system it ran under could even
be loaded, probably.
-s
D
Dik T. Winter
That is worst case (e.g. the stuff is already sorted). However that is
extremely pessimistic compared to the mean.
J
James Kuyper
Albert said:
Well, I can agree with that. I've never seen a compiler provide any kind
of qsort(). The standard library provides qsort(). Some standard library
functions (such as memcpy()) are often inlined by the compiler, but
qsort() isn't usually one of them. For this purpose, "implementation"
would be a better term than "compiler"; it includes the compiler, the
library, the linker, along with everything else you need to get a C
program to execute, including the supporting hardware and (if
applicable) the operating system.
Talking about "the" time complexity implies that there's only one time
complexity class allowed, in which case providing a supporting reference
would be possible only if was a reference to a part of the C standard
which said so. It would never have occurred to me, with your wording,
that you were aware that the complexity is not mandated, and were in
fact interested in an answer that only describes what common
implementations do.
U
user923005
Have you read :
Bentley, Jon L., "The Trouble With Qsort.",
UNIX Review. 10.2 (1992): 85-90.
Compilers generally do not document anything about their qsort
implementation other than the interface, which is documented in the
ANSI/ISO specifications anyway.
Some compilers do provide the source code for their implementation of
qsort.
Many implementations of the qsort function use introspective sort.
Plauger's implementation is excellent.
Here is what you can say about the qsort function, without fear of
contradiction:
"Since the qsort function uses comparisons for ordering of the data
items, the best possible theoretical performance is O(log(N!)) which
is O(N*log(N))."
See, for instance:
http://en.wikipedia.org/wiki/Comparison_sort