Re: question on sorting algorithms
From: Mel Wilson (mwilson_at_the-wire.com)
Date: 11/29/03
- Next message: Gerry Quinn: "Re: Any experience with "The Last One"?"
- Previous message: Sheldon Simms: "Re: Writing an Emulator"
- In reply to: Alexander Korovyev: "question on sorting algorithms"
- Next in thread: NFish: "Re: question on sorting algorithms"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sat, 29 Nov 2003 16:05:48 -0500
In article <26c82787.0311290847.60c0ea1b@posting.google.com>,
korovyev@rambler.ru (Alexander Korovyev) wrote:
>What sorting algorithms are there that are particularly well suited
>for sequences with many repeating elements. For example consider a
>sequence of one million numbers that has only 30 different numbers in
>it. My favorite algorithm shows unacceptably poor performance in this
>setting.
Well, if you know it's like that, counting the
occurrences and outputing the appropriate number of copies
in order will give you a sort that's O(2*n + 30*log(30)).
Jon Bentley mentions something like this in _Programming
Pearls_.
Regards. Mel.
- Next message: Gerry Quinn: "Re: Any experience with "The Last One"?"
- Previous message: Sheldon Simms: "Re: Writing an Emulator"
- In reply to: Alexander Korovyev: "question on sorting algorithms"
- Next in thread: NFish: "Re: question on sorting algorithms"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
