By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,170 Members | 1,053 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,170 IT Pros & Developers. It's quick & easy.

Fastest sort algorithm?

P: n/a
Hi,

I have a structure of 3 16-bit values. I have either 65000, 256000 or 1
million instances of this structure. I want to sort the lot of them
according to the number contained in one of the fields. Duplicate
values are allowed. So obviously if many instances of the structure
have the same value in this field, they must be together but they can be
in any order. The instances are already weakly sorted.

On modern Pentium 4/Athlon/G5, what would be the fastest algorithm to
use, and does anyone have any pointers to a fast implementation?
Jul 23 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
REH

"Richard Cavell" <ri***********@mail.com> wrote in message
news:d2*********@nnrp.waia.asn.au...
Hi,

I have a structure of 3 16-bit values. I have either 65000, 256000 or 1
million instances of this structure. I want to sort the lot of them
according to the number contained in one of the fields. Duplicate
values are allowed. So obviously if many instances of the structure
have the same value in this field, they must be together but they can be
in any order. The instances are already weakly sorted.

On modern Pentium 4/Athlon/G5, what would be the fastest algorithm to
use, and does anyone have any pointers to a fast implementation?


This is OT, but I'll try and help. You data set is probably prohibitively
large for all O(n) sort except for the Radix sort. I would also look at the
introspection sort (O(n log n)). How sorted is your weakly sorted data?
There are sorts that are or approach O(n) if the data is close to being
already sorted.

I have C++ implementation of many sorts, including three O(n) sorts, but not
here at work. If you like, I can email them to you this evening.

REH
Jul 23 '05 #2

P: n/a
On 1/4/05 12:48 AM, REH wrote:
This is OT, but I'll try and help. You data set is probably prohibitively
large for all O(n) sort except for the Radix sort. I would also look at the
introspection sort (O(n log n)). How sorted is your weakly sorted data?
My data looks like a sawtooth waveform when graphed out (not perfectly
so, but definitely that sort of shape). I'm trying to get it into a
perfect ramp.
I have C++ implementation of many sorts, including three O(n) sorts, but not
here at work. If you like, I can email them to you this evening.


Yes please.
Jul 23 '05 #3

P: n/a
REH

"Richard Cavell" <ri***********@mail.com> wrote in message
news:d2**********@nnrp.waia.asn.au...
On 1/4/05 12:48 AM, REH wrote:
This is OT, but I'll try and help. You data set is probably prohibitively large for all O(n) sort except for the Radix sort. I would also look at the introspection sort (O(n log n)). How sorted is your weakly sorted data?


My data looks like a sawtooth waveform when graphed out (not perfectly
so, but definitely that sort of shape). I'm trying to get it into a
perfect ramp.
I have C++ implementation of many sorts, including three O(n) sorts, but not here at work. If you like, I can email them to you this evening.


Yes please.


I didn't see your reply until I got to work this morning, so I'll send them
this evening. Each sort is encapsulated in a class, with traits that
defines such things as its performance, stability, in-place sorting, etc.
This is also a test program that times each sort and records the number of
swaps and compares (if appl.).

REH
Jul 23 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.