 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Here is an implementation of the quicksort algorithm in pov. It uses
recurisve macro calls.
It sorted 10000 numbers in less than a minute. With megapov it goes
about twice as fast.
Hope it is of some use.
- Micha Riser
-------------- begin code ------------------------------
#declare a=array[10000]
////////////////////////////////////////////////////////
#macro Quicksort(L,R)
#local i=L;
#local j=R;
#local c=a[int((L+R)/2)];
#while(i<j)
#while(a[i]<c) #local i=i+1; #end
#while(a[j]>c) #local j=j-1; #end
#if (i<j)
#local tmp=a[i];
#declare a[i]=a[j];
#declare a[j]=tmp;
#local i=i+1;
#local j=j-1;
#end
#end
#if (i=j) #local i=i+1; #local j=j-1; #end
#if (L<j) Quicksort(L,j) #end
#if (i<R) Quicksort(i,R) #end
#end
/////////////////////////////////////////////////////////////
#declare my_seed=seed(0);
#local i=0;
#while(i<10000)
#declare a[i]=rand(my_seed)*10000;
#local i=i+1;
#end
#debug "starting quick sort\n"
Quicksort(0,9999)
#debug "finished.\n"
#local i=0;
#while(i<10000)
#debug str(a[i],3,3)
#debug "\n"
#local i=i+1;
#end
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
hehe ... ever tried to implement BOZO-Sort ???
I've heard about it and laught...
Goes like this:
1) test if the array is in the order.
2) if not then
3) a=rand(Arraysize)
4) b=rand(Arraysize)
5) swap(a,b)
6) goto 1
7) else ready
... the one who told me about that said also something that prooves, the
termination of the algorithm' if a GOOD! randomizer is used ...
I don't really know, but I think it has a kewl runtime ;-)
--
Jan Walzer
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Micha Riser" <mri### [at] datacomm ch> wrote in message
news:3A5### [at] datacommch...
> Here is an implementation of the quicksort algorithm in pov. It uses
> recurisve macro calls.
>
> It sorted 10000 numbers in less than a minute. With megapov it goes
> about twice as fast.
Not bad! It sorted in ~15 sec.s on my computer (400mhz) so I increased
it by a factor of 10 and it did it in 195 seconds.
Takes -way- longer to display the debug info than to do the sort...
This may be very useful, but not for what I was doing, I finished that
yesterday. It turned out that I spent much longer figuring out the sort than
I would have spent just typing in some "random" numbers...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Bill Dewitt wrote:
> Takes -way- longer to display the debug info than to do the sort...
Of course. It's in Windows, in a tiny scrolling frame, with a tile behind it...
--
David Fontaine <dav### [at] faricynet> ICQ 55354965
My raytracing gallery: http://davidf.faricy.net/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"David Fontaine" <dav### [at] faricynet> wrote in message
news:3A529176.A451A3DF@faricy.net...
> Bill Dewitt wrote:
>
> > Takes -way- longer to display the debug info than to do the sort...
>
> Of course. It's in Windows, in a tiny scrolling frame, with a tile behind
it...
Eh... even with messages turned off, it takes way longer.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Jan Walzer <jan### [at] lzernet> wrote:
: ... the one who told me about that said also something that prooves, the
: termination of the algorithm' if a GOOD! randomizer is used ...
I have the feeling that it's not possible to make algorithmically a
random number generator that is so good that the array gets sorted in a
finite time for any finite array size. I might be wrong, of course.
: I don't really know, but I think it has a kewl runtime ;-)
Even with a perfect random number generator it sounds like the average
runtime would be infinite... Weird.
--
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Bill Dewitt" <bde### [at] cflrrcom> wrote in message
news:3a526b16$1@news.povray.org...
> yesterday. It turned out that I spent much longer figuring out the sort
than
> I would have spent just typing in some "random" numbers...
>
Well, the 3 virtues of the programmer are: laziness, hubris and impatience.
Put this one down to hubris (and you've got yourself some re-usable code).
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Jan Walzer <jan### [at] lzernet> wrote:
> : ... the one who told me about that said also something that prooves, the
> : termination of the algorithm' if a GOOD! randomizer is used ...
>
> I have the feeling that it's not possible to make algorithmically a
> random number generator that is so good that the array gets sorted in a
> finite time for any finite array size. I might be wrong, of course.
>
> : I don't really know, but I think it has a kewl runtime ;-)
>
> Even with a perfect random number generator it sounds like the average
> runtime would be infinite... Weird.
hehe ... sounds kewl:
the average! runtime is infinite ... (of course, I think so) but:
this would mean, that if there are cases with runtime < oo then there have
to be other cases with a runtime > oo, but what is greater than oo ??? Yes
there certain qualities of infinity, but if you think the normal way and not
in such a mathematically weird way *g*
...
--
Jan Walzer ...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
