l*********s
发帖数: 5409 | 1 [question] what is the time complexity of qsort in standard c libarary(GCC,
more specifically)? Is is based on quick sort algorithm? |
t****t
发帖数: 6806 | 2 theoretically it's not specified, but usually it's based on quick sort (see
the name). so it's O(NlogN) on average.
,
【在 l*********s 的大作中提到】
: [question] what is the time complexity of qsort in standard c libarary(GCC,
: more specifically)? Is is based on quick sort algorithm?
|
l*********s
发帖数: 5409 | 3 Thank you!
see
【在 t****t 的大作中提到】
: theoretically it's not specified, but usually it's based on quick sort (see
: the name). so it's O(NlogN) on average.
:
: ,
|
f*******n
发帖数: 12623 | 4 assuming it's quick sort, quick sort is O(n log n) average-case, and O(n^2)
worst-case |
d****n
发帖数: 1637 | 5 That would be only the partial answer.
if the sequence/array to be sorted has very good randomness(pivot good),
then the O(Nlog(N)).
if the array has been almost sorted or bad chose of pivot, the run time
would be O(N^2).
The Glib C qsort is a text-book implementation, which is terrible slow on
sorting on huge data set.
See introsort. or C++ stl::sort if you are looking for a industry solution. |
l*********s
发帖数: 5409 | 6 Thank you! How about qsort in GCC?
【在 d****n 的大作中提到】
: That would be only the partial answer.
: if the sequence/array to be sorted has very good randomness(pivot good),
: then the O(Nlog(N)).
: if the array has been almost sorted or bad chose of pivot, the run time
: would be O(N^2).
: The Glib C qsort is a text-book implementation, which is terrible slow on
: sorting on huge data set.
: See introsort. or C++ stl::sort if you are looking for a industry solution.
|
