Re: A Fast sorting algorithm for almost sorted data
- From: Phil Carmody <thefatphil_demunged@xxxxxxxxxxx>
- Date: 06 May 2007 22:29:10 +0300
Ben Rudiak-Gould <br276deleteme@xxxxxxxxx> writes:
Phil Carmody wrote:
moogie <budgetanime@xxxxxxxxxxxxxx> writes:
I would love to use better sorting algorithms. can you give me a goodJust get TAoCP. As I said before, Knuth's the man.
search string to try in google?
I don't think TAOCP describes introsort (C++'s std::sort), which is
probably the best comparison-based sorting algorithm for most
applications.
Knuth points the reader to Bentley&McIlroy. I've never seen
an input that that wasn't fast on, so never saw the need for
introsort. Most of the problems with quicksort going haywire
are pivot selection, and a 9-pseudomedian prevents anything
too wild happening (though is wasteful for small vectors, so
fall back to a 3-median).
Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.
.
- References:
- A Fast sorting algorithm for almost sorted data
- From: moogie
- Re: A Fast sorting algorithm for almost sorted data
- From: Phil Carmody
- Re: A Fast sorting algorithm for almost sorted data
- From: moogie
- Re: A Fast sorting algorithm for almost sorted data
- From: Phil Carmody
- Re: A Fast sorting algorithm for almost sorted data
- From: Ben Rudiak-Gould
- A Fast sorting algorithm for almost sorted data
- Prev by Date: Re: A Fast sorting algorithm for almost sorted data
- Next by Date: what happened to Iterated Systems Incorporated
- Previous by thread: Re: A Fast sorting algorithm for almost sorted data
- Next by thread: Re: A Fast sorting algorithm for almost sorted data
- Index(es):
Relevant Pages
|
|
