Q:Fastest sorting algorithm in c
Achilles Anagnostopoulos
I am using bubble sort but unfortunately it's too slow. Can anyone tell
me the fastest algorithm in C?
TIA
Russ Williams
Achilles Anagnostopoulos wrote in message
<34B32BC7...@geocities.com>...
>I am using bubble sort but unfortunately it's too slow. Can anyone tell
>me the fastest algorithm in C?
There is no 'fastest' - it depends *very* much on the circumstances
and implementation.
There is, however, a very good solution built into the C libraries -
qsort. This does a quicksort (*much* faster than a bubble sort,
particularly when sorting lots of values) on any data type (you need
to define a compare function, though).
Here's a sample of how to use it:
----- CUT HERE -----
#include <stdio.h>
#include <stdlib.h>
int compare( const void *arg1, const void *arg2 );
int myarray[8]={1,37,5,12,99,69,-15,0};
main() {
int i;
printf("Unsorted: ");
for (i=0;i<8;i++) printf("%d\t",myarray[i]);
printf("\n");
qsort( (void *)myarray, /* array of items to sort */
(size_t)8, /* number of elements */
sizeof(int), /* size of an element */
compare ); /* comparison function */
printf("Sorted: ");
for (i=0;i<8;i++) printf("%d\t",myarray[i]);
printf("\n");
return 0;
}
int compare( const void *arg1, const void *arg2 ) {
/* Compare routine for 2 ints */
int val1,val2;
val1=*(int *)arg1; val2=*(int *)arg2;
if (val1==val2) return 0;
else if (val1<val2) return -1;
else return 1;
/* Note that this would also work as 'return (val1-val2);' */
}
----- CUT HERE -----
If you want to know more about sorting, get a good book on algorithms.
Knuth's "Art of Computer Programming" has a volume on "Sorting and
Searching" (volume 3, IIRC).
---
Russ
d-range!
Russ Williams <ru...@algorithm.demon.co.uk> wrote in article
<6901mm$nsl$1...@flex.news.pipex.net>...
> Achilles Anagnostopoulos wrote in message
> <34B32BC7...@geocities.com>...
> >I am using bubble sort but unfortunately it's too slow. Can anyone tell
> >me the fastest algorithm in C?
>
> There is no 'fastest' - it depends *very* much on the circumstances
> and implementation.
>
> There is, however, a very good solution built into the C libraries -
> qsort. This does a quicksort (*much* faster than a bubble sort,
> particularly when sorting lots of values) on any data type (you need
> to define a compare function, though).
>
Well, Russ, we meet again ;) And know I'm sure why your DOS code is
outperformed by the DirectX version. You actually had to do something
yourself: a sorting algorithm. heheh.
Ok, Achilles, I'll explain to you a sorting algorithm called 'bucket
sorting' (or called 'radix sorting' often) - which is about twice as fast
(up to 500% faster if you're sorting a lot of elements) than bubble or
quicksorting
It goes like this: Suppose you have 4 16-bit values. in hex:
0101h, 040fh, 020Fh and 0001h. Now look at the values as being made up of
two 8-bit components: the high byte and the low byte (01h and 01h for the
first number, 04h and 0fh for the second etc).
Now sorting is very easy: the lowbyte/highbyte both run from 0 to 255, so
we construct 256 'buckets'.
Now we commence sorting - first the lowbytes, in pseudo-code:
for (DistLoop=1; DistLoop<NumValues; DistLoop++)
{
TheByte=lowbyte(Value[DistLoop]);
Bucket[TheByte]=Value[DistLoop];
}
now your buckets look like this - the lowbyte of a value specifies the
bucket it goes into :
bucket 1: bucket 2: [... for all empty buckets] bucket f:
0101h EMPTY 040fh
0001h 020fh
copy the buckets linearly back to your buffer whith the original values and
it will look like this now: 0101h, 0001h, 040fh, 020fh.
Almost ready.
Do the loop above again, but now let the highbyte specify the bucket a
value goes in, you'll get:
bucket 0: bucket 1: bucket 2: bucket 3: bucket 4:
0001h 0101h 020fh EMPTY 040fh
empty the buckets linearly in you value-buffer again and voila:
0001h, 0101h, 020fh,040fh -> sorted, in only 2 loops, while
bubble/quicksort needs 4+3+2+1=10 loops. time increases exponentially. But
not with bucket sorting: it's linear time, and it's easy.
To implement:
- set up the buckets (256 (2^8) for 16 bit values, 16 (2^4) for 8 bit
values etc)
- Distribute the values by lowbyte.
- empty the buckets in your value-buffer.
- Distribute the values by highbyte.
- empty the buckets in your value-buffer.
Bucket sorting takes only 2.5% of the frametime in my engine when sorting
about 2200 faces. Not too shabby isn't it ?
I think I've been quite clearly, so you'll understand how to implement, but
if you don't, gimme a call (or rather an email ;)
Greets,
d-range! <d-r...@thefridge.et.fnt.hvu.nl>
Russ: Have a lot of pleasure coding slow algorithms, but please don't
bother us again with your 'knowledge of what is fast and when' if you don't
know shit about coding.
Anthony D. Tribelli
d-range! (d-r...@thefridge.et.fnt.hvu.nl) wrote:
: Russ Williams <ru...@algorithm.demon.co.uk> wrote in article
: > Achilles Anagnostopoulos wrote in message
: > >I am using bubble sort but unfortunately it's too slow. Can anyone tell
: > >me the fastest algorithm in C?
: >
: > There is no 'fastest' - it depends *very* much on the circumstances
: > and implementation.
[SNIP]
: Ok, Achilles, I'll explain to you a sorting algorithm called 'bucket
: sorting' (or called 'radix sorting' often) - which is about twice as fast
: (up to 500% faster if you're sorting a lot of elements) than bubble or
: quicksorting
Russ was correct in that "fastest" is dependent on circumstances. If
someone needs to write a sorting algorithm I strongly suggest they start
by reading Knuth's The Art of Computer Programming, Sorting and Searching,
then understand the program and the characteristics of the data expected,
then pick an algorithm.
Tony
--
------------------
Tony Tribelli
adtri...@acm.org
Ziqiang Tang
And d-range, if this was meant to be a personal attack, have
decency to keep it in private mail to Russ. For a beginner,
using qsort instead of implementing bucket sort makes a lot
of sense (as a starting point), and you might confuse some poor
guy trying to write Tetris into writing 200 lines of code for no reason.
Anthony D. Tribelli wrote in message ...
>d-range! (d-r...@thefridge.et.fnt.hvu.nl) wrote:
>: Russ Williams <ru...@algorithm.demon.co.uk> wrote in article
>: > Achilles Anagnostopoulos wrote in message
>
>: > >I am using bubble sort but unfortunately it's too slow. Can anyone
tell
>: > >me the fastest algorithm in C?
>: >
>: > There is no 'fastest' - it depends *very* much on the circumstances
>: > and implementation.
>
>[SNIP]
>
>: Ok, Achilles, I'll explain to you a sorting algorithm called 'bucket
>: sorting' (or called 'radix sorting' often) - which is about twice as fast
>: (up to 500% faster if you're sorting a lot of elements) than bubble or
>: quicksorting
>
William H. Ivey
In <6901mm$nsl$1...@flex.news.pipex.net> "Russ Williams"
<ru...@algorithm.demon.co.uk> writes:
>
[...]
>There is, however, a very good solution built into the C libraries -
>qsort. This does a quicksort (*much* faster than a bubble sort,
>particularly when sorting lots of values) on any data type (you need
>to define a compare function, though).
>
>
>int compare( const void *arg1, const void *arg2 ) {
> /* Compare routine for 2 ints */
> int val1,val2;
>
> val1=*(int *)arg1; val2=*(int *)arg2;
>
> if (val1==val2) return 0;
> else if (val1<val2) return -1;
> else return 1;
>/* Note that this would also work as 'return (val1-val2);' */
>}
Here's an interesting bit of trivia that is seldom stressed about the
library version of qsort(). The two pointers passed to the compare
function may not point into your data array. The only time I've seen
this become a problem is when a friend of mine, looking to trap array
overruns, tested the pointers with the array limits. Worked for months
until the size of the array hit some magic number and one of the
pointers pointed to a temporary variable within qsort() instead of the
array. (This was in Watcom, BTW.)-Wm
Russ Williams
d-range! wrote in message <01bd1bbc$9df32080$LocalHost@faktor21>...
>Russ Williams <ru...@algorithm.demon.co.uk> wrote in article
><6901mm$nsl$1...@flex.news.pipex.net>...
>> Achilles Anagnostopoulos wrote in message
>> <34B32BC7...@geocities.com>...
>> >I am using bubble sort but unfortunately it's too slow. Can anyone tell
>> >me the fastest algorithm in C?
>>
>> There is no 'fastest' - it depends *very* much on the circumstances
>> and implementation.
>>
>> There is, however, a very good solution built into the C libraries -
>> qsort. This does a quicksort (*much* faster than a bubble sort,
>> particularly when sorting lots of values) on any data type (you need
>> to define a compare function, though).
>
>Well, Russ, we meet again ;)
Indeed.
>And know I'm sure why your DOS code is outperformed by the DirectX
>version. You actually had to do something yourself: a sorting algorithm.
>heheh.
I responded to a beginner's question with a simple, concise answer.
I never said qsort was perfect, only that it's good. I could have wittered
on for pages about different kinds of sorts, but I posted a simple
answer and a pointer to more information (Knuth).
As for the DOS code: Yup. You're absolutely right. I just used
DirectSort under Windows and it went a lot faster...
>Ok, Achilles, I'll explain to you a sorting algorithm called 'bucket
>sorting' (or called 'radix sorting' often) - which is about twice as fast
>(up to 500% faster if you're sorting a lot of elements) than bubble or
>quicksorting
500%, huh? Where'd you get that figure from?
[Radix sort]
It's just a pity that a radix sort needs either far more memory (number
of buckets * number of items) or a linked list. And how well does it
perform on strings (say, up to 256 chars long)?
>Russ: Have a lot of pleasure coding slow algorithms, but please don't
>bother us again with your 'knowledge of what is fast and when' if you
>don't know shit about coding.
If you knew shit about sorting, you'd know that it's impossible to sort
arbitrary data in better than n log n time (eg: quicksort). The radix
sort is fine for integers but is not a panacea. Given that Achilles didn't
happen to mention what he's sorting, a radix sort may be woefully
inadequate. It may not. Who knows?
IMHO, one of the most likely things to be sorting would be polygons.
A bucket sort works well there, but a BSP tree will usually beat it and
will fuck up a damn sight less.
---
Russ
Roger Nixon
Russ Williams wrote:
> If you knew shit about sorting, you'd know that it's impossible to sort
> arbitrary data in better than n log n time (eg: quicksort). The radix
> sort is fine for integers but is not a panacea. Given that Achilles didn't
> happen to mention what he's sorting, a radix sort may be woefully
> inadequate. It may not. Who knows?
Actually, a quicksort is only expected nlogn, not order nlogn.
Russ Williams
Roger Nixon wrote in message <34B49A...@nope.dev.madge.com>...
Yup. It degenerates into an insert sort in the worst case, IIRC.
O(n^2) in any case. That's why many implementations use the
'median of 3' rule to find the splitting point... It still fucks up on
sorted data, though.
It's not as good as, say, a merge sort in the worst case - but the
main reason for choosing qsort it is that it's usually fast and it's
implemented in stdlib...
As always: know your data.
---
Russ
d-range!
Ziqiang Tang <zt...@parker.eecs.berkeley.edu> wrote in article
<4xVs.699$0S6.1...@news.inreach.com>...
> And d-range, if this was meant to be a personal attack, have
> decency to keep it in private mail to Russ.
Well, He did'nt keep his personal attacks private too. Follow 'will dos
die' to find uit yourself.
> For a beginner, using qsort instead of implementing bucket sort makes a
lot
> of sense (as a starting point), and you might confuse some poor
> guy trying to write Tetris into writing 200 lines of code for no reason.
>
Bucket sort isn't a bit harder then quicksort. And I took the time to
explain it well. Even my little brother understands it after reading the
post. And by the way, Achilles wanted to know what the FASTEST method was,
not the easiest. And the fact he could implement a working bubble sort
means to me he'll understand bucketsorting as well.
regards,
d-range! <d-r...@thefridge.et.fnt.hvu.nl>
d-range!
Russ Williams <ru...@algorithm.demon.co.uk> wrote in article
<6925d0$qmn$1...@flex.news.pipex.net>...
> d-range! wrote in message <01bd1bbc$9df32080$LocalHost@faktor21>...
> >Russ Williams <ru...@algorithm.demon.co.uk> wrote in article
> ><6901mm$nsl$1...@flex.news.pipex.net>...
> >> Achilles Anagnostopoulos wrote in message
> >> <34B32BC7...@geocities.com>...
> >> >I am using bubble sort but unfortunately it's too slow. Can anyone
tell
> >> >me the fastest algorithm in C?
> >>
> >
> >Well, Russ, we meet again ;)
>
> Indeed.
>
> >And know I'm sure why your DOS code is outperformed by the DirectX
> >version. You actually had to do something yourself: a sorting algorithm.
> >heheh.
>
> I responded to a beginner's question with a simple, concise answer.
> I never said qsort was perfect, only that it's good. I could have
wittered
> on for pages about different kinds of sorts, but I posted a simple
> answer and a pointer to more information (Knuth).
>
He asked for the fastest sorting algorithm, so I gave it.
> As for the DOS code: Yup. You're absolutely right. I just used
> DirectSort under Windows and it went a lot faster...
>
But you don't even know why. You don't understand the key elements of your
code, so you're a lousy coder. You'll probably don't even know how a
quicksort works, or how to fill a polygon. not mentioned texture mapping,
phong shading etc.
> >Ok, Achilles, I'll explain to you a sorting algorithm called 'bucket
> >sorting' (or called 'radix sorting' often) - which is about twice as
fast
> >(up to 500% faster if you're sorting a lot of elements) than bubble or
> >quicksorting
>
> 500%, huh? Where'd you get that figure from?
>
D0h0h0, I experienced it. If my 3d engine took about half an hour to render
a scene with bubblesorting, and now does it at 70 fps, then were talking
hell of a lot more than 500%. It mayb 10% faster for 100 faces, or 100% for
1000, but for 3000 faces it's as least as 500% faster. But You'll probably
never notice, coz you don't know how to write one.
>
> [Radix sort]
>
> It's just a pity that a radix sort needs either far more memory (number
> of buckets * number of items) or a linked list. And how well does it
> perform on strings (say, up to 256 chars long)?
Indeed, a linked list sized NumValues*sizeof(short). w000w, that'ts a lot
of memory. And what are you complaining about 256 byte strings. For a
computer 'a string' is the same as 'a series of bytes'. so thay can be
sorted equally fast.
>
> >Russ: Have a lot of pleasure coding slow algorithms, but please don't
> >bother us again with your 'knowledge of what is fast and when' if you
> >don't know shit about coding.
>
> If you knew shit about sorting, you'd know that it's impossible to sort
> arbitrary data in better than n log n time (eg: quicksort). The radix
> sort is fine for integers but is not a panacea.
It looks as if you don't know shit about coding, and you don't know shit
about computers too. A computer stores all his data in integer format fool.
Except for floating point values, but you can convert them to integers too.
(And you would have to do that with quicksort too so...). Bucket sorting
can be done for bytes, words, dwords, qwords, you name it - it only depends
on the size you take for a single chunk. 4 bit, 8 bits etc, and the number
of passes you want. The more passes, the less memory - the bigger the chunk
size, the faster. So if you think sorting always takes n log n, then you
are sorting the wrong way. Bucketsorting time increases linearly.
> Given that Achilles didn't
> happen to mention what he's sorting, a radix sort may be woefully
> inadequate. It may not. Who knows?
A radix sort is already faster than a quicksort with as few as 20 values.
Because it uses no compares, only 2 loops with 16-bit values. The only
thing a radix sort does is moving the values 4 times, first to the buckets,
back to the value buffer, again distribute them to the buckets and finally,
copy them sorted back to the valuebuffer.
So 'woefully inadequate' it will never be.
>
> IMHO, one of the most likely things to be sorting would be polygons.
> A bucket sort works well there, but a BSP tree will usually beat it and
> will fuck up a damn sight less.
BSP trees are ten times as complicated to code, and fuck up if the walls or
objects move.
Like if you can use a BSP tree for a dynamical array of values. Who said
the sorting algorithm needs to be tailored to what you are sorting? If
there's only one 'sorting' algorithm (actually it doesn't sort anything at
all) that's restricted in it's uses, it is BSP trees.
d-range! <d-r...@thefridge.et.fnt.hvu.nl>
James Shaw
"d-range!" <d-r...@thefridge.et.fnt.hvu.nl> wrote:
>You don't understand the key elements of your
>code, so you're a lousy coder. You'll probably don't even know how a
>quicksort works, or how to fill a polygon. not mentioned texture mapping,
>phong shading etc.
What's that got to do with sorting?
>It looks as if you don't know shit about coding, and you don't know shit
>about computers too. A computer stores all his data in integer format fool.
>Except for floating point values, but you can convert them to integers too.
>(And you would have to do that with quicksort too so...).
Why?
The advantage of quicksort over radix sort is that you don't have to
copy the data (or swap pointers) all the time, only when a swap is
necessary.
Jim
Russ Williams
d-range! wrote in message <01bd1c63$085b8ec0$6d89f1c3@faktor21>...><6925d0$qmn$1...@flex.news.pipex.net>...
>> d-range! wrote in message <01bd1bbc$9df32080$LocalHost@faktor21>...
>> >> >I am using bubble sort but unfortunately it's too slow. Can anyone
>> >> >tell me the fastest algorithm in C?
>> I responded to a beginner's question with a simple, concise answer.
>> I never said qsort was perfect, only that it's good. I could have
>> wittered on for pages about different kinds of sorts, but I posted a
>> simple answer and a pointer to more information (Knuth).
>
>He asked for the fastest sorting algorithm, so I gave it.
Except that it isn't. The 'fastest' depends on the implementation and the
data used. There is no single answer.
Your suggested radix (4-bit) would require 8 passes to sort ints.
That's 8*n comparisons.
A quicksort would (usually) require n*log2(n) compares. Thus, a
quicksort (or a merge sort, or any similar) would likely be faster for
<256 values.
If you wanted to sort 3 values, an unrolled bubble sort is probably best.
There is no 'fastest' sort algorithm
>> As for the DOS code: Yup. You're absolutely right. I just used
>> DirectSort under Windows and it went a lot faster...
>
>But you don't even know why.
I'm taking the piss. Didn't you realise that? Somehow I doubt MS are
ever going to release a DirectSort.
>You don't understand the key elements of your code,
What do you call 'key elements'?
>so you're a lousy coder.
That's a pretty strong accusation. Do you have anything to back that up?
>You'll probably don't even know how a quicksort works, or how to fill a
>polygon. not mentioned texture mapping, phong shading etc.
Anything nontrivial? I have no interest in trying to prove to you that I'm
at least competant.
>> >Ok, Achilles, I'll explain to you a sorting algorithm called 'bucket
>> >sorting' (or called 'radix sorting' often) - which is about twice as
>> >fast (up to 500% faster if you're sorting a lot of elements) than
>> >bubble or quicksorting
>>
>> 500%, huh? Where'd you get that figure from?
>
>D0h0h0, I experienced it.
Oh, well that must make it accurate, then.
>If my 3d engine took about half an hour to render a scene with
>bubblesorting, and now does it at 70 fps, then were talking hell of a lot
>more than 500%. It mayb 10% faster for 100 faces, or 100% for
>1000, but for 3000 faces it's as least as 500% faster.
There's a branch of maths to do with that, you know.
>But You'll probably never notice, coz you don't know how to write one.
You seem pretty sure of yourself.
>> [Radix sort]
>>
>> It's just a pity that a radix sort needs either far more memory (number
>> of buckets * number of items) or a linked list. And how well does it
>> perform on strings (say, up to 256 chars long)?
>
>Indeed, a linked list sized NumValues*sizeof(short). w000w, that'ts a lot
>of memory.
No, it's not. It's only 4 bytes/element for the chaining, which is nothing.
The speed hit comes from *walking* the linked list and having to add
nodes to the middle. That's a lot slower than array accesses.
It's particularly bad for a radix sort, since items have to be added to a
bucket in order from previous buckets. That means either double
linking or walking the full length of each bucket list to find the tail.
>And what are you complaining about 256 byte strings. For a
>computer 'a string' is the same as 'a series of bytes'. so thay can be
>sorted equally fast.
[Note: When I say digit below, I refer to the sort keys for a bucket.
Digits, letters, whatever]
Did you really understand the radix sort? It only works when you sort
from LSD to MSD.
I'd better give you an example:
cat, car, bat
Sort on last digit: r{car}, t{cat,bat}
Sort on middle digit: a{car, cat, bat}
Sort on first digt: b{bat}, c{car, cat}
bat, car, cat.
You have to check the digits in reverse order and retain the ordering
of buckets between passes. k-digit elements require k passes.
For reference, a quicksort would do the same as:
cat, car, bat
{bat, car},{cat}
{{bat}, {car}},{cat}
bat, car, cat
That, BTW, is only 2 passes. The radix sort required 3. Imagine the
difference on 256 char strings...
>> >Russ: Have a lot of pleasure coding slow algorithms, but please
>> >don't bother us again with your 'knowledge of what is fast and
>> >when' if you don't know shit about coding.
>>
>> If you knew shit about sorting, you'd know that it's impossible to
>> sort arbitrary data in better than n log n time (eg: quicksort). The
>> radix sort is fine for integers but is not a panacea.
>
>It looks as if you don't know shit about coding, and you don't know shit
>about computers too.
I'm sorry, I don't think I follow that logic...
>A computer stores all his data in integer format fool. Except for floating
>point values,
So, computers store everything as integers, except the things that aren't
stored as integers. I think I've got that...
>but you can convert them to integers too.
How handy.
>(And you would have to do that with quicksort too so...).
Why? Did Intel break FP compares and not tell anyone?
Quicksorts work on anything that can have 'less than' defined
on it - and if you can't define 'less than', sorting them into order
would be pretty fucking tricky...
>Bucket sorting can be done for bytes, words, dwords, qwords, you
>name it - it only depends on the size you take for a single chunk.
>4 bit, 8 bits etc, and the number of passes you want.
>The more passes, the less memory - the bigger the chunk
>size, the faster.
Yes. That's obvious. What about the fact that most sorting methods
just look at pairs of elements and decide what to do with them?
Integer compares are implemented very well on most CPUs, so why
would you want to ignore such a resource?
>So if you think sorting always takes n log n, then you
>are sorting the wrong way. Bucketsorting time increases linearly.
It doesn't work on arbitrary data. It's impossible to use a radix sort on
arbitrary length strings, for example. You have to specify the number
of passes and then sort what falls between the buckets seperately.
Most sort routines only need to check the first few characters to
decide the relative order of 2 strings. A radix sort needs to check
every single one.
>> Given that Achilles didn't happen to mention what he's sorting, a
>> radix sort may be woefully inadequate. It may not. Who knows?
>
>A radix sort is already faster than a quicksort with as few as 20 values.
>Because it uses no compares,
Compares are cheap.
>only 2 loops with 16-bit values.
Sure, but the list setup would castrate the CPU. 20 values in 65536
buckets? *Very* efficient. That would pretty much require walking the
whole list to place an element (ie: an insert sort), since the overhead
of generating a list through 64k entry nodes would be ridiculous.
>The only thing a radix sort does is moving the values 4 times, first to
>the buckets, back to the value buffer, again distribute them to the
>buckets and finally, copy them sorted back to the valuebuffer.
If your CPU has hardware buckets.
In reality, the overhead of maintaining 64k buckets would kill it. Hell, for
20 items, a bubble sort would be faster.
>So 'woefully inadequate' it will never be.
Really? Your example seems to be an ideal case of where it fucks up...
>> IMHO, one of the most likely things to be sorting would be polygons.
>> A bucket sort works well there, but a BSP tree will usually beat it and
>> will fuck up a damn sight less.
>
>BSP trees are ten times as complicated to code, and fuck up if the
>walls or objects move.
They're trivial to code. Binary trees are easy. As for the moving, yes,
that's their main problem. They're still better than bucket sorting in
many cases.
Walls, in my experience, don't often move. YMMV.
>Like if you can use a BSP tree for a dynamical array of values. Who
>said the sorting algorithm needs to be tailored to what you are
>sorting?
Anyone who knows what they're talking about?
>If there's only one 'sorting' algorithm (actually it doesn't sort anything
>at all) that's restricted in it's uses, it is BSP trees.
All sorting algorithms have their problems. BSP trees are very good for
what they do.
It is possible to calculate BSP-like trees in real-time - you just have to
insert polys into a binary tree (approx. log2(n) compares to find where
it goes). It would offer near-infinite precision in the sorting, so many
of the bucket sort artifacts would disappear.
---
Russ
Chris Lomont
d-range! wrote in message <01bd1c4e$e99ab920$7989f1c3@faktor21>...
Bucket sort is not the fastest. Again it depends on your data. For
example, here's a case used in professional games where bubble sort of
all things is faster than bucket sort:
If you have a list where everything except a few adjacent items are
sorted, bubble sort will correct those on one pass. Bucket sort takes
a lot more overhead on this one. This is often used for sprite depth
sorting where as sprites move from frame to frame, a sorted list is
kept of their depth. Between frames, sprites change places on the
depth list in pairs, so a single pass bubble sort works extremely well
for these applications. It beats qsort and radix (bucket) sort hands
down, since they want to sort the entire data set, even though it is
mostly sorted.
Think before you try to claim any sorting is absolutely best.
And don't attack others for posting other solutions. Yours is not best
for many, many cases.
Chris Lomont
Chris Lomont
d-range! wrote in message <01bd1c63$085b8ec0$6d89f1c3@faktor21>...
>
>
>> >> >I am using bubble sort but unfortunately it's too slow. Can
anyone
>tell
>> >> >me the fastest algorithm in C?
>> >>
>> >Well, Russ, we meet again ;)
>>
>> Indeed.
>>
>> >And know I'm sure why your DOS code is outperformed by the DirectX
>> >version. You actually had to do something yourself: a sorting
algorithm.
>> >heheh.
>>
>> I responded to a beginner's question with a simple, concise answer.
>> I never said qsort was perfect, only that it's good. I could have
>wittered
>> on for pages about different kinds of sorts, but I posted a simple
>> answer and a pointer to more information (Knuth).
>>
>
>He asked for the fastest sorting algorithm, so I gave it.
As posted elsewhere, your solution is not the fastest for many cases.
>> As for the DOS code: Yup. You're absolutely right. I just used
>> DirectSort under Windows and it went a lot faster...
>>
>
>But you don't even know why. You don't understand the key elements of
your
>code, so you're a lousy coder. You'll probably don't even know how a
>quicksort works, or how to fill a polygon. not mentioned texture
mapping,
>phong shading etc.
You must also be a lousy coder by your own standards, since you
obviously don't understand that some sorting routines are better than
others depending on the data and problem. Radix sort is not the best,
as I posted in reply to another of your posts.
>> >Ok, Achilles, I'll explain to you a sorting algorithm called
'bucket
>> >sorting' (or called 'radix sorting' often) - which is about twice
as
>fast
>> >(up to 500% faster if you're sorting a lot of elements) than
bubble or
>> >quicksorting
>>
>> 500%, huh? Where'd you get that figure from?
>>
>
>D0h0h0, I experienced it. If my 3d engine took about half an hour to
render
>a scene with bubblesorting, and now does it at 70 fps, then were
talking
>hell of a lot more than 500%. It mayb 10% faster for 100 faces, or
100% for
>1000, but for 3000 faces it's as least as 500% faster. But You'll
probably
>never notice, coz you don't know how to write one.
Use interframe coherency or a BSP tree to get similar speedups. A
speedup of 500% in a program by changing one sort routine does not
necessarily mean the sort routine is 500% faster. This is pretty
simple logic. If you insist on flaming here be prepared to receive a
little yourself.
>>
>> [Radix sort]
>>
>> It's just a pity that a radix sort needs either far more memory
(number
>> of buckets * number of items) or a linked list. And how well does
it
>> perform on strings (say, up to 256 chars long)?
>
>Indeed, a linked list sized NumValues*sizeof(short). w000w, that'ts a
lot
>of memory. And what are you complaining about 256 byte strings. For a
>computer 'a string' is the same as 'a series of bytes'. so thay can
be
>sorted equally fast.
And you take a big cache hit by sorting that big a chunk of memory
each frame, which translates to a performance hit. Perhaps if you
rethought your algorithms a bit.....
>> >Russ: Have a lot of pleasure coding slow algorithms, but please
don't
>> >bother us again with your 'knowledge of what is fast and when' if
you
>> >don't know shit about coding.
>>
>> If you knew shit about sorting, you'd know that it's impossible to
sort
>> arbitrary data in better than n log n time (eg: quicksort). The
radix
>> sort is fine for integers but is not a panacea.
>
>It looks as if you don't know shit about coding, and you don't know
shit
>about computers too. A computer stores all his data in integer format
fool.
>Except for floating point values, but you can convert them to
integers too.
>(And you would have to do that with quicksort too so...). Bucket
sorting
>can be done for bytes, words, dwords, qwords, you name it - it only
depends
>on the size you take for a single chunk. 4 bit, 8 bits etc, and the
number
>of passes you want. The more passes, the less memory - the bigger the
chunk
>size, the faster. So if you think sorting always takes n log n, then
you
>are sorting the wrong way. Bucketsorting time increases linearly.
Only given data that maps into your range. Radix sort (or bucket sort)
can sort N records with b-bit keys in b/m passes using 2^m memory
locations. So for large datasets you need more memory, and there comes
a tradeoff where other methods are superior. You must have read
someone's web page claiming radix to be the solution to every sorting
problem but cannot reason it out for yourself.
>> Given that Achilles didn't
>> happen to mention what he's sorting, a radix sort may be woefully
>> inadequate. It may not. Who knows?
>
>A radix sort is already faster than a quicksort with as few as 20
values.
>Because it uses no compares, only 2 loops with 16-bit values. The
only
>thing a radix sort does is moving the values 4 times, first to the
buckets,
>back to the value buffer, again distribute them to the buckets and
finally,
>copy them sorted back to the valuebuffer.
Radix is faster for random datasets, but if you know something about
your data (like sorted polys are almost sorted from frame to frame of
a game) you can beat radix sort.
>> IMHO, one of the most likely things to be sorting would be
polygons.
>> A bucket sort works well there, but a BSP tree will usually beat it
and
>> will fuck up a damn sight less.
>
>BSP trees are ten times as complicated to code, and fuck up if the
walls or
>objects move.
You avoid them because their complicated, and have the nerve to flame
others? Doom and Quake use BSP trees and have quite good performance,
since they're not sorting the world each frame.
And you can easily add moving objects to the world.
>Like if you can use a BSP tree for a dynamical array of values. Who
said
>the sorting algorithm needs to be tailored to what you are sorting?
If
>there's only one 'sorting' algorithm (actually it doesn't sort
anything at
>all) that's restricted in it's uses, it is BSP trees.
And BSP trees sort the world faster than radix sort, but I guess your
misguided attachment to radix sort will keep you out of the high
performance engine area.
Chris Lomont
Paul Shirley
In article <691m1f$o...@dfw-ixnews8.ix.netcom.com>, "William H. Ivey"
<wi...@ix.netcom.com> writes
>Here's an interesting bit of trivia that is seldom stressed about the
>library version of qsort(). The two pointers passed to the compare
>function may not point into your data array. The only time I've seen
>this become a problem is when a friend of mine, looking to trap array
>overruns, tested the pointers with the array limits. Worked for months
>until the size of the array hit some magic number and one of the
>pointers pointed to a temporary variable within qsort() instead of the
>array. (This was in Watcom, BTW.)-Wm
Its not a feature of qsort but a bug in the implementation. I believe
djgpp had a similar problem.
---
Paul Shirley: my email address is 'obvious'ly anti-spammed
Paul Hsieh
ru...@algorithm.demon.co.uk says...
True, it is also *in-place* meaning it requires no additional storage,
which can be a consideration if you are trying to sort a set of records
that cannot be held in memory. But in terms of video games this is
unlikely to be an issue.
> As always: know your data.
Yes, but usually as a side effect of this, the better you know your data,
the more attractive other sorting algorithms such as Radix sort or bubble
sort (depending on your data organization) become. QuickSort is rarely
the best choice execpt for expediency of implementation as you indicated.
--
Paul Hsieh
q...@chromatic.com
William H. Ivey
In <KAVoBOAO...@foobar.co.uk> Paul Shirley <Pa...@no.spam.please>
writes:
>In article <691m1f$o...@dfw-ixnews8.ix.netcom.com>, "William H. Ivey"
><wi...@ix.netcom.com> writes
>>Here's an interesting bit of trivia that is seldom stressed about the
>>library version of qsort(). The two pointers passed to the compare
>>function may not point into your data array
>
>Its not a feature of qsort but a bug in the implementation. I believe
>djgpp had a similar problem.
>
At the time, at least, we couldn't find anything to indicate that
the pointers supplied to the compare function were required to point
into the array (the phrase "points to an array element" is marginally
ambiguous). It seems to be implementation dependant, not a bug.-Wm
Chris Palmer
In article <696dre$j...@sjx-ixn6.ix.netcom.com>,
That is correct. The linux standard library (version 5.4.23) actually
implements qsort using a merge sort algorithm. Comparisons are done in
the temporary array which is the behaviour that you noticed. I suspect
that the OSF 3.2 libraries also use a merge sort because they definitely
require additional storage. (One tends to notice these things when sorting
50MB arrays on a machine with 64MB ram)
qsort, as opposed to quicksort, means to sort the input array quickly.
It does not imply an algorithm.
Cheers,
Chris.
--
Mail: crpa...@undergrad.uwaterloo.ca
Homepage: http://www.undergrad.math.uwaterloo.ca/~crpalmer/
Russ Williams
Paul Hsieh wrote in message ...
>ru...@algorithm.demon.co.uk says...
[...]
>> It's not as good as, say, a merge sort in the worst case - but the
>> main reason for choosing qsort it is that it's usually fast and it's
>> implemented in stdlib...
>True, it is also *in-place* meaning it requires no additional storage,
>which can be a consideration if you are trying to sort a set of records
>that cannot be held in memory. But in terms of video games this is
>unlikely to be an issue.
Just as side note: I can't think of many games-related applications
for sorting (that are time critical - league tables, etc. are pretty
irrelevant). There's the typical zsort and sprite order examples, but
I can't think of much that would require you to sort n arbitrary values
more than, like, once per level - and that includes sprites and polys
most of the time.
>> As always: know your data.
>
>Yes, but usually as a side effect of this, the better you know your
>data, the more attractive other sorting algorithms such as Radix
>sort or bubble sort (depending on your data organization) become.
Bubble sorts are pretty much ideal in lots of game-related
applications, where things change very little between frames.
>QuickSort is rarely the best choice execpt for expediency of
>implementation as you indicated.
As someone else pointed out, some compilers do qsort as a merge
sort, which is a bit better. The whole point is not reinventing the wheel
unless you can do it better...
And writing a sort that gets called once a minute by hand isn't usually
a good use of time (if it's too slow, precalculation might be a better
bet...).
---
Russ
Paul Shirley
>In <KAVoBOAO...@foobar.co.uk> Paul Shirley <Pa...@no.spam.please>
>writes:
>>
>>In article <691m1f$o...@dfw-ixnews8.ix.netcom.com>, "William H. Ivey"
>><wi...@ix.netcom.com> writes
>>>Here's an interesting bit of trivia that is seldom stressed about the
>>>library version of qsort(). The two pointers passed to the compare
>>>function may not point into your data array
>[...]
>>
>>Its not a feature of qsort but a bug in the implementation. I believe
>>djgpp had a similar problem.
>>
>
>At the time, at least, we couldn't find anything to indicate that
>the pointers supplied to the compare function were required to point
>into the array (the phrase "points to an array element" is marginally
>ambiguous). It seems to be implementation dependant, not a bug.-Wm
The last report of this behaviour involved calls with pointers to the
value one past the array end which was very definetly a bug (because
there's no guarantee that any memory is mapped there).
You are correct to say it makes no explicit guarantees on pointing into
your array (in my documentation at least). In fact it does not promise
to send pointers to any element of the array ;)
William H. Ivey
In <q2fAsIAq...@foobar.co.uk> Paul Shirley <Pa...@no.spam.please>
writes:
re: qsort() and the pointers it sends to the compare function:
>The last report of this behaviour involved calls with pointers to the
>value one past the array end which was very definetly a bug (because
>there's no guarantee that any memory is mapped there).
We traced it back into the library's disassembly and found it pointing
to a stack variable used as temporary storage - as I'd guessed, since
the value of the pointer was so far from the array's bounds.-Wm
Dave Kirby
On 8 Jan 1998 18:30:35 GMT, "d-range!"
<d-r...@thefridge.et.fnt.hvu.nl> wrote:
[snip...]
>It looks as if you don't know shit about coding, and you don't know shit
>about computers too. A computer stores all his data in integer format fool.
>Except for floating point values, but you can convert them to integers too.
>(And you would have to do that with quicksort too so...). Bucket sorting
>can be done for bytes, words, dwords, qwords, you name it - it only depends
>on the size you take for a single chunk. 4 bit, 8 bits etc, and the number
>of passes you want. The more passes, the less memory - the bigger the chunk
>size, the faster. So if you think sorting always takes n log n, then you
>are sorting the wrong way. Bucketsorting time increases linearly.
Sure, all data can be treated as a series of bytes but presumably you
are sorting the data for a purpose, such as displaying it in sorted
order to the user. In that case the bucket sort algorithm you posted
may not work since although it will sort it into an order, it isnt
necessarily the order you want. Hell, as it stands it wont even work
for signed ints, let alone floats or pointer to chars (or anything
else). There is not much point in sorting an array of pointers on the
pointer value (i.e. the order in which the items pointed to occur in
memory) if the user is expected strings sorted alphabetically.
Bucket sorting CAN be fastest for some data, but that doesn't make it
the fastest or best for all cases and it is cannot be made general
purpose - it has to be re-written for each data type. I would always
use qsort (in C) or STL sort (in C++) first, and only worry about
replacing it with something special purpose if that proved inadequate.
In some cases it may be better not to sort at all. For example if you
are sorting the data so that you can search it later it may be better
to use a hash table which can have both constant time insertion and
searching.
It is never a good idea to fixate on 'the one best way of doing xxx'
since you invariably end up with a mind closed to potentially better
alternatives.
Dave K
________________________________________________
Communication is only possible between equals.
dave@ <-figure this out, spambots!-> Dave.Kirby@
dkirby. psygnosis.
demon. My opinions are my own, co.uk
co.uk but I'm willing to share.
Amit Patel
| >I am using bubble sort but unfortunately it's too slow. Can anyone tell
| >me the fastest algorithm in C?
|
| and implementation.
Agreed.
| There is, however, a very good solution built into the C libraries -
| qsort. This does a quicksort (*much* faster than a bubble sort,
| particularly when sorting lots of values) on any data type (you need
| to define a compare function, though).
Just an addendum:
If you are using C++ (and yes, I realize the original poster is using
C and not C++), you might want to use the sort function included with
STL. (STL's sort is a quicksort or something similar.) I find that
it's five times as fast as qsort() when sorting integers, because it
avoids all the overhead of comparing two values though a function
call, and swapping elements of unknown data size.
| Here's a sample of how to use it:
|
| ----- CUT HERE -----
| #include <stdio.h>
| #include <stdlib.h>
|
| int compare( const void *arg1, const void *arg2 );
|
| int myarray[8]={1,37,5,12,99,69,-15,0};
|
| main() {
| int i;
|
| printf("Unsorted: ");
| for (i=0;i<8;i++) printf("%d\t",myarray[i]);
| printf("\n");
Here, you'd just use this instead:
sort(myarray, myarray+8);
| printf("Sorted: ");
| for (i=0;i<8;i++) printf("%d\t",myarray[i]);
| printf("\n");
|
| return 0;
| }
(With STL, you wouldn't need the compare function if you're using the
default < operator.)
I generally find STL's algorithms to be faster _and_ easier to use
(which is a rare combination!) than C's algorithms (qsort, bsearch).
- Amit
Russ Williams
Amit Patel wrote in message <69h9mg$dk4$1...@nntp.Stanford.EDU>...
[STL sort / RTL qsort]
>(With STL, you wouldn't need the compare function if you're using
>the default < operator.)
For arbitrary types, you'd still need to define <. That's no worse than
for C, though.
>I generally find STL's algorithms to be faster _and_ easier to use
>(which is a rare combination!) than C's algorithms (qsort, bsearch).
I should think it's also typesafe - as opposed to void pointer casts.
---
Russ
Thatcher Ulrich
In article <69h9mg$dk4$1...@nntp.Stanford.EDU>, Amit Patel
am...@Xenon.Stanford.EDU says...
> Russ Williams <ru...@algorithm.demon.co.uk> wrote:
> | Achilles Anagnostopoulos wrote in message
> | <34B32BC7...@geocities.com>...
> | >I am using bubble sort but unfortunately it's too slow. Can anyone tell
> | >me the fastest algorithm in C?
> |
> | There is no 'fastest' - it depends *very* much on the circumstances
> | and implementation.
>
> Agreed.
Just to throw in my 2 cents:
If the compare function is simple (i.e. comparing two integers), I've
found a radix sort can be extremely fast. In recent titles I've
replaced the merge sort I originally used with a radix sort for
sorting primitives. At the time I made the switch, frames typically
contained between 500 and 2000 primitives. The merge sort was taking
5 ms for a typical frame, whereas the equivalent radix sort took under
1 ms. Maybe my merge sort sucked (I don't think so; I profiled it and
optimized it on a couple of occasions, although I never compared
against qsort()), but based on my experience I'd say radix sort is
worth a look if sorting time is an issue. Also, radix is O(n) rather
than O(nlogn), so the advantage will improve with an increase in
elements.
--
Thatcher Ulrich
http://world.std.com/~ulrich
Amit Patel
I agree; the article I posted was more about different library
implementations of a single algorithm rather than comparing two
different algorithms. In particular, the C library routine "qsort" is
significantly slower than the C++ routine "sort" for small data
elements and cheap comparisons, because there is a lot of overhead of
calling the compare function and also overhead for swapping two
elements. Instead of:
if data[a] < data[b]
t = data[a]
data[a] = data[b]
data[b] = t
you get (for C's qsort):
if (*compare)(data+a*element_size,data+b*element_size) < 0
for i = 0; i < element_size; i++
t = data[a*element_size+i]
data[a*element_size+i] = data[b*element_size+i]
data[b*element_size+i] = t
Yes, you can optimize that loop, BUT it's not going to be as efficient
as three simple assignments, at least for things like 32-bit words.
Similarly, for a radix sort, if you have small data elements or fast
compares, you should look at the implementation you are using and make
sure it's specializing (like C++'s STL library) and not using a single
implementation with loops to move elements around, like what I showed
above.
Anyway, back to our regularly scheduled flaming! :(
- Amit