The sort in <algorithm> of c++

[remlostime]

Is the sort in <algortithm> the quick_sort, and O(nlogn) ?

 

[Kai-Uwe Bux]

Is the sort in <algortithm> the quick_sort, and O(nlogn) ?

a) Quick_sort is not O(n log(n)) in worst case complexity, but O( n^2 ). It
is only O(n log(n)) on average with regard to the uniform distribution on
input sequences of length n.

b) The standard permits that std::sort() be implemented as quick_sort, but
you can find other implementations, as well. I have seen introsort, which
is about as fast as quick_sort on average and, in addition, is O(n log(n))
even in the worst case. I think, even the old reference implementation from
HP and SGI may have used introsort, which could have propagated from there.
You can find introsort, for instance, in Stlport and in the standard
library that ships with g++.

c) This is a quality of implementation issue. In my experience, it is _very_
hard to beat std::sort().


Best

Kai-Uwe Bux

 

[Alf P. Steinbach]

* remlostime:

Is the sort in <algortithm> the quick_sort

Not specified.

, and O(nlogn) ?

Yes, sort of. It's guaranteed to be a stable sort, and the complexity
is described as "Approximately N log N". However, what that means (is
it a worst case guarantee, or just an average?) seems to not be defined.

 

[Neelesh Bodas]

* remlostime:

Yes, sort of. It's guaranteed to be a stable sort,

std::stable_sort is guaranteed to be a stable sort. Is std::sort also
guaranteed to be a stable sort?

-N

 

[remlostime]

a) Quick_sort is not O(n log(n)) in worst case complexity, but O( n^2 ). It
is only O(n log(n)) on average with regard to the uniform distribution on
input sequences of length n.

b) The standard permits that std::sort() be implemented as quick_sort, but
you can find other implementations, as well. I have seen introsort, which
is about as fast as quick_sort on average and, in addition, is O(n log(n))
even in the worst case. I think, even the old reference implementation from
HP and SGI may have used introsort, which could have propagated from there.
You can find introsort, for instance, in Stlport and in the standard
library that ships with g++.

c) This is a quality of implementation issue. In my experience, it is _very_
hard to beat std::sort().

Best

Kai-Uwe Bux

Thank u for your meaningful answers, and i have learned more about it

 

[Alf P. Steinbach]

* Neelesh Bodas:

std::stable_sort is guaranteed to be a stable sort. Is std::sort also
guaranteed to be a stable sort?

No. Sorry, I thought this was about std::list::sort.

Must have been some carry-over in my association subsystem, from some
earlier thread here.

 

[remlostime]

a) Quick_sort is not O(n log(n)) in worst case complexity, but O( n^2 ). It
is only O(n log(n)) on average with regard to the uniform distribution on
input sequences of length n.

b) The standard permits that std::sort() be implemented as quick_sort, but
you can find other implementations, as well. I have seen introsort, which
is about as fast as quick_sort on average and, in addition, is O(n log(n))
even in the worst case. I think, even the old reference implementation from
HP and SGI may have used introsort, which could have propagated from there.
You can find introsort, for instance, in Stlport and in the standard
library that ships with g++.

c) This is a quality of implementation issue. In my experience, it is _very_
hard to beat std::sort().

Best

Kai-Uwe Bux

I have learned that you introduct the introsort algorithm, and how can
i use it, which header include it?

 

[Kai-Uwe Bux]

std::stable_sort is guaranteed to be a stable sort. Is std::sort also
guaranteed to be a stable sort?

No: the standard was worded vaguely on std::sort() to allow quick_sort. But
std::stable_sort() is not only stable, it is also has O(n log(n)) worst
case complexity.


Best

Kai-Uwe Bux

 

[osmium]

* remlostime:

Not specified.



Yes, sort of. It's guaranteed to be a stable sort, and the complexity is
described as "Approximately N log N". However, what that means (is it a
worst case guarantee, or just an average?) seems to not be defined.

I would infer that "approximately" means "average".

On a similar subject, did you ever see those TV commercials for money making
schemes: "Earn an average of up to $4K per month?" That's a magic number
that is both average *and* a best case! What's that all about? ISTM some
government agency should put a stop to such nonsensical claims.

 

[Kai-Uwe Bux]

I have learned that you introduct the introsort algorithm,

I did not introduce introsort. That algorithm is due to David R Musser. The
paper is online at:

http://www.cs.rpi.edu/~musser/gp/introsort.ps

It was published in: Software--Practice and Experience, Vol. 27(8) August
1997, pp. 983-993. It also introduces introselect, which is a linear time
algorithm for nth_element using the same ideas.

and how can i use it, which header include it?

Chances are that your std::sort() already uses introsort. Since most
compilers do not support export, you can probably check that by reading
through the files pulled by the header <algorithm>.


Best

Kai-Uwe Bux

 

[Alf P. Steinbach]

* osmium:

I would infer that "approximately" means "average".

Perhaps, probably. But please note that I was mistakenly taking about
std::list::sort (as mentioned else-thread). Stuck in an earlier thread...

 

[Michael Ekstrand]

I have learned that you introduct the introsort algorithm, and how can
i use it, which header include it?

The STL does not specify which sorting algorithm is in use, or how to
specify a particular one. So, look at the documentation for your
compiler and STL implementation to see which sorting alogrithm they use.
They may offer non-standard extensions to access alternative sorting
algorithms, but those are just that - non-standard.

As noted in point B above, if you're using SGI's STL implementation (or
a derived implementation, such as that provided with GCC), then
std::sort *is* introsort. You don't have to do anything to get
introsort.

- Michael

 

[Gernot Frisch]

On a similar subject, did you ever see those TV commercials for
money making
schemes: "Earn an average of up to $4K per month?" That's a magic
number that is both average *and* a best case! What's that all
about? ISTM some government agency should put a stop to such
nonsensical claims.

If you're the only one with that job, and your income is $4k, then
it's the average _and_ the best case. Thus, this little hint give a
quite detailed description of the job.

 

[BobR]

If you're the only one with that job, and your income is $4k, then
it's the average _and_ the best case. Thus, this little hint give a
quite detailed description of the job.

100% of the people I interviewed want bush impeached.
(hint: I only interviewed one person. <G>)

I really get annoyed when news people give percentages, but not the base!
It's a politician trick, "unemployment is down to 4%", but we all know it's
*much* higher because they only use the people collecting unemployment
insurance as the base. Many of us don't get counted! (U.S.A, I don't know
about other countries.)

[ sorry for OT. I knew some day I could wedge in this rant! <G> ]