I've been trying to do a simple sort, but it doesn't seem to be working as I
remember. What am I doing wrong?

 #declare R1 = seed(321321);

 #declare Spread = array[6]
 /// populate
 #declare I = 0;
 #while ( I < 5 )
  #declare Spread[I] = rand(R1);
 #declare I = I+1;
 #end
 /// verify
 #declare I = 0;
 #while ( I < 5 )
  #debug concat(str(Spread[I],2,2), "\n")
 #declare I = I+1;
 #end
 #debug "\n"
 /// sort
 #declare I = 0;
 #while ( I < 5 )
 #declare First  = Spread[I];
    #declare P = I+1;
    #while (P < 5)
      #declare Second = Spread[P];
       #if ( Second < First )
       #declare Storage = First;
       #declare First   = Second;
       #declare Second  = Storage;
       #end
    #declare P = P+1;
    #end
 #declare I = I+1;
 #end
 /// re-display
 #declare I = 0;
 #while ( I < 5 )
 #debug concat(str(Spread[I],2,2), "\n")
 #declare I = I+1;
 #end

Post a reply to this message

On Mon, 1 Jan 2001 17:46:47 -0500, "Bill Dewitt" <bde### [at] cflrrcom> wrote:

>I've been trying to do a simple sort, but it doesn't seem to be working as I
>remember. What am I doing wrong?
>
Not putting in comments to tell us what is going on!
----------------------
dav### [at] hamiltonitecom
http://hamiltonite.com/

Post a reply to this message

Bill Dewitt <bde### [at] cflrrcom> wrote:
> I've been trying to do a simple sort, but it doesn't seem to be working as
I
> remember. What am I doing wrong?
[code snipped]

The mistake comes in trying to use the First and Second variables as if they
were pointers (i.e. your code assumes modifying these two variables will
modify the original array members you declared them to).  If you change the
code not to use these variables:

#declare I = 0; #while ( I < 5 )
   #declare P = I+1; #while (P < 5)
      #if (Spread[P] < Spread[I])
         #declare Storage = Spread[I];
         #declare Spread[I]   = Spread[P];
         #declare Spread[P]  = Storage;
      #end
   #declare P = P+1; #end
#declare I = I+1; #end

you should find it works as expected.

Post a reply to this message

"Chris Colefax" <chr### [at] tagpovrayorg> wrote :
>
>  (i.e. your code assumes modifying these two variables will
> modify the original array members you declared them to).

< Slaps head > Thanks...

Post a reply to this message

By the way, that's one of the slowest way of sorting an array...

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

Warp wrote:
>   By the way, that's one of the slowest way of sorting an array...

But bubble sorting is the easiest for a lot of people to understand and
write :)

My brother gave me a big lecture about different array sorting methods, like
binary search tree etc...

How easy is it to implement something like that with POV-Ray?

--
Lance.

http://come.to/the.zone

Post a reply to this message

On Mon, 1 Jan 2001 18:25:17 -0500, Bill Dewitt wrote:
>
>"Chris Colefax" <chr### [at] tagpovrayorg> wrote :
>>
>>  (i.e. your code assumes modifying these two variables will
>> modify the original array members you declared them to).
>
>< Slaps head > Thanks...

A slap head with false teeth! Don't sound much like a Viking to me. 

-- 
Cheers
Steve              email mailto:ste### [at] zeroppsuklinuxnet

%HAV-A-NICEDAY Error not enough coffee  0 pps. 

web http://www.zeropps.uklinux.net/

or  http://start.at/zero-pps

 11:05am  up 14 days, 22:27,  3 users,  load average: 1.39, 1.22, 1.10

Post a reply to this message

"Warp" <war### [at] tagpovrayorg> wrote in message
news:3a51b517@news.povray.org...
>   By the way, that's one of the slowest way of sorting an array...

    Well... being as how I am only sorting 6 things....

    But if you would like to publish an array sorting macro, I will use it
with great happiness and thanks.

Post a reply to this message

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