When making my latest 3D program, I noticed that one thing that was taking a LOT of speed out of my program was the Z sorting routine. I am currently using a sorting routine that goes similar to this:
Code:
FOR i = 1 to num
FOR sort = 1 to num-1
IF array(sort) < array(sort + 1) THEN SWAP array(sort), array(sort + 1)
NEXT
NEXT
Is this a bubblesort?
This works fine for what I need, but for large 3D models, it is sloooow, because it obvvously takes n^2 loops, where n is the number of polys, so the time increases exponentialy.
I need a quicksort. I gather from the name that it is well... quick. So how do they work? Are they complicated and are they suitable for what I need?
Thanks...
Included in one of the qb45 packages form nathans
www.download-qb.tk there's an example program, showing alot of sorting methods, both the source ofcause, but also show graphically how they work.
Ok, thanks but the example doesnt actually explain how the Quicksort works. It only gives the code and has a couple of comments which I dont really understand.
and damn... I never knew there were so many ways of searching...
I think this may help
Code:
DIM MyArray(1 to 900) AS INTEGER 'Just To See how fast it is....
i1% = 0
i2% = i1% + 1
looped% = -1
DO
if i1% = 0 then looped% = looped% + 1
i1% = (i1% + 1) MOD 900
i2% = (i1% + 1) MOD 900
if MyArray(i1%) > MyArray(i2%) then
SWAP MyArray(i1%), MyArray(i2%)
end of
LOOP UNTIL looped% = 5
This code is untested, but should be fairly reliable and a little faster
Alex~
Quote:... Is this a bubblesort?
Your code is similar to a bubble sort but it's missing a "control" which tests if any swaps were made and avoids testing these elements again.
Here's a bubble sort by Sumojo, which is written for strings, but which you can easily convert. The control I mentioned is the Flag$ in this case. You can use any kind of switch. Setting the Flag$ to "no" means I had to do a swap 'cause some elements were out of sequence.
Remember that even a good bubble sort is still going to be faily slow, For you, it might be an improvement.
Code:
rem Bubble Sort by sumojo 04Feb2003
While Flag$ <> "yes"
Flag$ = "yes"
For x = 1 to 'amount of words/numbers to be sorted minus 1
If Ucase$(Word(x)) > Ucase$(Word(X+1)) then
Swap Word(x), Word(x+1)
Flag$ = "no"
end if
next x
wend
*****
I've always used this version, which gives a O(n) = n + (n-1) + (n-2) + ... instead of the posted solutions which are O(n) = n^2 (which means that in the worst case, for example with 8 elements, you would have 36 iterations instead of 64). This is the most efficient version of the bubblesort algorithm, released in the 70s I think.
Code:
FOR i%=0 TO n%
FOR j%= 0 TO n%-i%
IF a(j%)>a(j%+1) THEN
SWAP a(j%), a(j%+1)
ENDIF
NEXT j%,i%
Quote:I've always used this version, which gives a O(n) = n + (n-1) + (n-2) + ... instead of the posted solutions which are O(n) = n^2 (which means that in the worst case, for example with 8 elements, you would have 36 iterations instead of 64). This is the most efficient version of the bubblesort algorithm, released in the 70s I think.
Cool. Ok , i realised after I posted about how to optimise the bubblesort, with the "- i%"
That does indeed make it a lot quicker.
Moneo: Thanks Ill check out the code
Alex: Thanks I will also check that out!
This is what I've taken to call the "mephisto sort" after the person who helped me put things together, and in reality did most of the work on it. It's actually a radix sort, but the version I use has been modified to work extensively on disk, allowing it to sort files thousands of times greater than available memory. The full routine I'm using can sort millions of large numbers in a minute or less, while using about 100k or less of memory, and it scales quite well. For 3000 records, on this machine, it's about 1 timer count, generally, when it registers at all (1/18.2 of a second).
http://www.network54.com/Forum/message?f...1078502520