Fastest sorting algorithm in C?
d-range!
First of all,believe me when I say I do not like flaming (although I don't
give a shit if someone who I don't even remotly know flames me), but some
people were asking for it - and when responding, you ask for it yourself
too. Different people have different opinions. But now back to sorting: To
prove how fast bucket sorting is - here's the source to my bucketsorter.
Try it yourself, and compare it to bubble/quicksort - and you'll see.
Greets,
d-range! <d-r...@thefridge.et.fnt.hvu.nl>
begin 600 Bucket.c
<encoded_portion_removed>
end
end
Chris Lomont
d-range! wrote in message <01bd1d0d$1cf2daa0$4f89f1c3@faktor21>...
>First of all,believe me when I say I do not like flaming (although I
don't
>give a shit if someone who I don't even remotly know flames me), but
some
>people were asking for it - and when responding, you ask for it
yourself
>too. Different people have different opinions. But now back to
sorting: To
>prove how fast bucket sorting is - here's the source to my
bucketsorter.
>Try it yourself, and compare it to bubble/quicksort - and you'll see.
Bubble sort is faster on lists already sorted or nearly sorted.
Your code has errors for large datasets since your buffers are static
sizes. Try to sort a mixture of 500 1's and 500 2's, for example.
The point the others and I were making is that bucket sort is fast,
but not fastest for every application. You need to understand the data
and use the sorting algorithm most useful for that data set.
Take the numbers 1 to 1,000,000, swap any number distinct pairs, and
bubble sort in one pass sorts the list. Your sort is much slower here
since it moves many, many items.
Chris Lomont
Russ Williams
d-range! wrote in message <01bd1d0d$1cf2daa0$4f89f1c3@faktor21>...
>First of all,believe me when I say I do not like flaming (although I
>don't give a shit if someone who I don't even remotly know flames
>me), but some people were asking for it - and when responding,
>you ask for it yourself too. Different people have different opinions.
>But now back to sorting: To prove how fast bucket sorting is - here's
>the source to my bucketsorter.
>Try it yourself, and compare it to bubble/quicksort - and you'll see.
Yup. Tried it. Here's the results:
VC5, default optimisations, your code vs. qsort sorting values
generated from unseeded rand() calls, RDTSC timing.
10 elements, qsort: ~2500 clocks, bucket: ~37500 clocks.
Yes, it's convoluted.
Yes, the bucket sort is faster for some other values.
Yes, it's enough to prove your assertion ("Bucket sort is the fastest
algorithm") to be false.
Maybe this stupid thread can die now?
---
Russ
d-range!
> >Try it yourself, and compare it to bubble/quicksort - and you'll see.
>
> Yup. Tried it. Here's the results:
>
> VC5, default optimisations, your code vs. qsort sorting values
> generated from unseeded rand() calls, RDTSC timing.
>
> 10 elements, qsort: ~2500 clocks, bucket: ~37500 clocks.
>
Could you please try it with >3000 values now? - thank you very much
d-range! <d-r...@thefridge.et.fnt.hvu.nl>
Russ Williams
d-range! wrote in message <01bd1e8f$1b606260$2189f1c3@faktor21>...
Why? It only takes that run to disprove your assertion.
You claimed that the radix sort is the fastest algorithm, this example
disproves that.
FYI, with 1000 values, the times were: ~275000 for bucket, ~435000 for
qsort.
---
Russ
KSG
Russ Williams wrote:
>
> d-range! wrote in message <01bd1e8f$1b606260$2189f1c3@faktor21>...
> >> >Try it yourself, and compare it to bubble/quicksort - and you'll see.
> >>
> >> Yup. Tried it. Here's the results:
> >>
> >> VC5, default optimisations, your code vs. qsort sorting values
> >> generated from unseeded rand() calls, RDTSC timing.
> >>
> >> 10 elements, qsort: ~2500 clocks, bucket: ~37500 clocks.
> >
> >Could you please try it with >3000 values now? - thank you very much
>
> Why? It only takes that run to disprove your assertion.
> You claimed that the radix sort is the fastest algorithm, this example
> disproves that.
First, I agree with what you were doing Russ, in showing that the best
sorting algorithm is dependant on things such as the problem size. I
don't get what you say though when you state: "You claimed that the
radix sort is the fastest algorithm". Where is the radix sort
algorithm? I thought the code you were looking at was a bucket sort?
Did I miss something?
Thanks,
--
KSG
Chris Lomont
KSG wrote in message <34B8E6...@cs.ucsd.edu>...
Radix and bucket sort are the same thing. Radix is the tech term for
the hash key to determine the bucket.
Chris Lomont
Su Jin
Chris Lomont wrote:
> Radix and bucket sort are the same thing. Radix is the tech term for
> the hash key to determine the bucket.
Me and Russ had this discussion offline (well online, but off of
usenet). I've always learned them to be two different algorithms,
although possibly similar (bucket sort possibly being a special case of
radix sort).
Let me quote from CLR some of the key features from Bucket Sort which I
think make it different from radix sort:
"Bucket sort assumes that thte input is generated by a random process
that distributes elements uniformly over the interval [0,1)."
"The idea of bucket sort is to divide the interval [0,1) into n
equal-sized subintervals, or buckets, and then distribute the n input
numbers into the buckets."
Radix sort is *independent* of n. Rather it creates its "buckets" as a
function of the radix of which you are using, not the problem size. Now
if you have a uniform distribution over the bits that represent the
number and you do your radix sort over the full radix of the type you
are sorting, then they are then essentially the same. (ie I have 64k
numbers from 0-64k and I have them stored as 16-bit integers, and then I
do 16-bit radix sort to sort them. This is essentially like a bucket
sort, at least in spirit.).
This is at least how I understand it. Russ and you seem to have the
same position on the two algorithms. So are there two schools of
thought on this?
--
KSG
Russ Williams
Su Jin wrote in message <34B9FC...@uclink4.berkeley.edu>...
[...]
>This is at least how I understand it. Russ and you seem to have the
>same position on the two algorithms. So are there two schools of
>thought on this?
At least 3 that I count. There's the 'special case of Radix', the 'divide
n items into f(n) buckets & insert sort' of CLR[1] and from a web
search, I found 'split items in [min..max] into k buckets and recurse'
from Gonnet/Baeza-Yates. Sedgewick seems to have avoided
bucket sorts, perhaps wisely.
It seems that 'bucket sort' means 'any sort that chucks values into
buckets'... :)
Does anyone have a copy of Knuth, volume 3? I think we should
probably defer to that, if anything.
---
Russ
[1] "Introduction to Algorithms" by Cormen, Lieserson & Rivest