Qbasicnews.com
April 04, 2020, 09:02:41 AM
 Welcome, Guest. Please login or register. 1 Hour 1 Day 1 Week 1 Month Forever Login with username, password and session length
 Home Help Search Login Register
 Pages: [1] 2
 Author Topic: Quicksort/ Bubblesort  (Read 6810 times)
KiZ
__/--\__

Posts: 2879

 « on: June 05, 2004, 08:39:05 AM »

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...
 Logged
Zap
Been there, done that

Posts: 1124

 « Reply #1 on: June 05, 2004, 08:47:47 AM »

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

url=http://www.copy-pasta.com]CopyPasta[/url] - FilePasta
KiZ
__/--\__

Posts: 2879

 « Reply #2 on: June 05, 2004, 10:11:59 AM »

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...
 Logged
Oz
I hold this place together

Posts: 923

 « Reply #3 on: June 05, 2004, 12:28:57 PM »

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~
 Logged
Moneo
Na_th_an

Posts: 1971

 « Reply #4 on: June 06, 2004, 12:03:47 AM »

Quote from: "dark_prevail"
... 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

*****
 Logged
na_th_an
*/-\*

Posts: 8244

 « Reply #5 on: June 06, 2004, 11:57:28 AM »

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

SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio
underBASIC, homegrown musicians
[img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
KiZ
__/--\__

Posts: 2879

 « Reply #6 on: June 06, 2004, 04:04:59 PM »

Quote from: "na_th_an"
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!
 Logged
Jonathan Simpson
Forum Regular

Posts: 140

 « Reply #7 on: June 06, 2004, 10:02:23 PM »

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?forumid=182035&messageid=1078502520
 Logged

onathan Simpson
speedlemon
I hold this place together

Posts: 874

 « Reply #8 on: June 06, 2004, 10:11:43 PM »

Quote from: "Jonathan Simpson"
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?forumid=182035&messageid=1078502520
:x
 Logged
Plasma
Na_th_an

Posts: 1770

 « Reply #9 on: June 07, 2004, 12:57:52 AM »

constipated?
 Logged
relsoft
*/-\*

Posts: 3927

 « Reply #10 on: June 07, 2004, 02:13:44 AM »

Quote from: "Plasma"
constipated?

ROTFLMAO
 Logged

y smiley is 24 bit.

Genso's Junkyard:
http://rel.betterwebber.com/
Oz
I hold this place together

Posts: 923

 « Reply #11 on: June 07, 2004, 10:00:59 AM »

Lol......thats exactly what came to mind when i read taht too..

*hands speedlemon sum [X]LAX*
*pats him on the back*
"Good Luck.... :evil: "

Alex~
 Logged
Moneo
Na_th_an

Posts: 1971

 « Reply #12 on: June 08, 2004, 11:36:27 PM »

Quote from: "na_th_an"
I've always used this version..........

It may be a great sort, but it's definitely not a bubblesort, because it has two for loops. Looks more like a shell-sort. Believe me, I've been coding bubblesorts for over 40 years, with 25 of them in assembler. Never used or saw anyone use two nested loops.

By the way, what everyone calls a bubblesort is really a sift-sort, because every time through the loop the large values "sift" down to the bottom of the list. For a real bubblesort, the small values "bubble" up to the top of the list. A little sort trivia.
*****
 Logged
na_th_an
*/-\*

Posts: 8244

 « Reply #13 on: June 09, 2004, 09:47:08 AM »

Well, that's what I was taught at college: "ordenacíón por burbuja"
And your algo also has two loops

If you look at yours, in the worst case the external loop (while) will loop N times, so it is almost the same. The "book" algo, in C, had something like this in the outter loop:

Code:
for(i=0; i<N && !flag; i++)

That is, it tries to count from 0 to N-1 while the flag is not set.

What I mean is that yours and mines is the same algorithm but using different syntax. When we were taught the sorting methods, the original bubblesort had two full loops, and the enhaced bubblesort was like the one I posted.

Note that the short definition of bubble-sort is:

Quote
Bubble sort: for each pair of indices, swap the items if out of order

You can code that in many ways.

Also;

http://www.free-definition.com/Bubble-sort.html
http://www.informationblast.com/Bubble_sort.html
 Logged

SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio
underBASIC, homegrown musicians
[img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
KiZ
__/--\__

Posts: 2879

 « Reply #14 on: June 09, 2004, 12:30:21 PM »

Remember, the speed depends on how many records you are sorting.

I made up a sorting type, which uses a method kind of like Quicksort, except its not that quick. (lol)..
When I compared it to a proper bubble sort, the bubble sort came faster. (for ~500 records)
Then I upped the records to 5000. My sorting type won (10 seconds) compared to 13.5 seconds for the bubblesort.
 Logged
 Pages: [1] 2