Lance Birch <-> wrote:
: But bubble sorting is the easiest for a lot of people to understand and
: write :)

  Actually insertion sort is a lot more intuitive than bubble sort.
  If you ask someone who doesn't know anything about sorting to make a
sorting algorithm, he will most probably make an insertion sort (or a very
close variant), not a bubble sort.
  Bubble sort is just awful. It's slow even for an O(n^2) algorithm.
Insertion sort is also an O(n^2) algorithm (that is, very slow), but quite
faster than bubble sort.

  O(n^2) algorithms are hopelessly slow when there are even a slight amount
of items (like 1000 or so). If one wants a good sorting algorithm, it's
necessary to use an O(n*log n) algorithm. Those beat O(n^2) algorithms 10-0
with large amount of items.
  A merge sort might be the easiest to implement in povray.

-- 
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

OK, I can see how an insertion algorithm is just as easy to make (and why
it's more intuitive).

But then again there's no real need to have it super fast anyway if it's
going to be just on the parse phase...

I understand all the stuff about O(n^2) and O(n*log n) too, he talked for a
fair while, hehe, actually I'm amazed I remember most of it... I wasn't
really paying attention at the time... hehe

--
Lance.

http://come.to/the.zone

Post a reply to this message

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] datacommch> 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