Qbasicnews.com

QBasic => QB Discussion & Programming Help => Topic started by: KiZ on June 05, 2004, 08:39:05 AM



Title: Quicksort/ Bubblesort
Post by: KiZ 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...


Title: Quicksort/ Bubblesort
Post by: Zap 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.


Title: Quicksort/ Bubblesort
Post by: KiZ 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...


Title: Quicksort/ Bubblesort
Post by: Oz 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~


Title: Re: Quicksort/ Bubblesort
Post by: Moneo 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

*****


Title: Quicksort/ Bubblesort
Post by: na_th_an 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%


Title: Quicksort/ Bubblesort
Post by: KiZ 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!


Title: Quicksort/ Bubblesort
Post by: Jonathan Simpson 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


Title: Quicksort/ Bubblesort
Post by: speedlemon 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
:o :o  :o  :x  :o  :o  :o


Title: Quicksort/ Bubblesort
Post by: Plasma on June 07, 2004, 12:57:52 AM
constipated?


Title: Quicksort/ Bubblesort
Post by: relsoft on June 07, 2004, 02:13:44 AM
Quote from: "Plasma"
constipated?


ROTFLMAO


Title: Quicksort/ Bubblesort
Post by: Oz 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~


Title: Quicksort/ Bubblesort
Post by: Moneo 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.
*****


Title: Quicksort/ Bubblesort
Post by: na_th_an on June 09, 2004, 09:47:08 AM
Well, that's what I was taught at college: "ordenacíón por burbuja" :P
And your algo also has two loops :P ;)

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


Title: Quicksort/ Bubblesort
Post by: KiZ 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.


Title: Quicksort/ Bubblesort
Post by: na_th_an on June 09, 2004, 02:30:04 PM
That has to do with the order of your algo. As I said, plain bubblesort implementations posted are O(n^2).


Title: Quicksort/ Bubblesort
Post by: Moneo on June 10, 2004, 12:21:36 AM
Nathan,
You keep mentioning "my" algo. The one I posted was written by Sumojo. It's fairly close to the way I would code a bubblesort, but the truth is that the last time I coded one was about 25 years ago in assembler.

Sumojo's version does not have the TWO FOR LOOPS that I said yours has. the outer loop does no processing and could be accomplished with an IF  xxx THEN GOTO TOP.

If I was really serious about coding a bubblesort, I would use the following:
Code:

'The Bubble Sort routine that follows uses a FOR/NEXT loop to repeatedly
'examine an array and exchange elements as necessary, until all of the items
'are in the correct order.

SUB BubbleSort (Array$()) STATIC

DO
  OutOfOrder = 0                      'assume it's sorted
  FOR X = 1 TO UBOUND(Array$) - 1
    IF Array$(X) > Array$(X + 1) THEN
      SWAP Array$(X), Array$(X + 1)   'if we had to swap
      OutOfOrder = 1                  'we may not be done
    END IF
  NEXT
LOOP WHILE OutOfOrder = 1

END SUB

'This routine is simple enough to be self-explanatory, and only a few things
'warrant discussing.  One is the OutOfOrder flag variable.  When the array
'is nearly sorted to begin with, fewer passes through the loop are needed.
'The OutOfOrder variable determines when no more passes are necessary.  It
'is cleared at the start of each loop, and set each time two elements are
'exchanged.  If, after examining all of the elements in one pass no
'exchanges were required, then the sorting is done and there's no need for
'the DO loop to continue.
'The other item worth mentioning is that the FOR/NEXT loop is set to
'consider one element less than the array actually holds.  This is necessary
'because each element is compared to the one above it.  If the last element
'were included in the loop, then BASIC would issue a "Subscript out of
'range" error on the statement that examines Array$(X + 1).


However, if speed was an issue I would use another algorithm like perhaps a quicksort, or most likely your algorithm Nathan, which, although it is not a pure bubblesort, looks simple enough and is probably much faster. Remember guys, the more sophisticated the algorithm you chose, the greater the chance of your implementation having some bug in it.
*****


Title: Quicksort/ Bubblesort
Post by: na_th_an on June 10, 2004, 09:28:43 AM
When I said "your algo" I meant "the algo you posted".

What I was trying to make clear is that both implementations are almost the same. You can name it LOOP or whatever. In assembly, the pair formed by an address and a JNZ address (for example) _is_ a loop. Just a matter of nomenclature. WHILE and DO structures are loops. st: ... IF c% THEN GOTO st: is a loop.

My whole point is that bubblesort is defined as "for each pair of indices, swap the items if out of order" (upon the mathematical definition) and simply you have many ways of coding it. I was not dissing the algorithm you posted, I was just saying that there is not the only implementation of it. You've been coding for 25 years a concrete implementation of the bubblesort. Simply, there are more.

The algorithm I posted works. It was developed by Dijkstra, I think, and I trust the man ;)

Anyhow, there are mathematical methods to tell if an algorithm is correct or not, based on Pre/post conditions (using logics and stuff like that). I've tested this algorithm for an exam years ago, and it is correct without restrictions. I can look for the test and post it here.

You will also realize that the way it works, in every iteration, the biggest number of the sub-vector analyzed goes to the last position, that's why you only need to loop until N-i%.


Title: Quicksort/ Bubblesort
Post by: KiZ on June 10, 2004, 11:18:39 AM
Yea moneo you are right, the algo I posted at the top was a sift sort. Pretty cool, mind.

And moneo, nathan never said sumo's algo had two FORNEXTs. He said it had two loops. Which is quite right. It did have two loops.


Title: Quicksort/ Bubblesort
Post by: Moneo on June 10, 2004, 11:30:07 PM
Nathan,
We seem not to understand each other.
You keep saying LOOP, and giving all kinds of examples.
I keep talking about FOR LOOPS.
Anyway...........forget it.

As for your pointing out that there are many ways to code a bubblesort ---- you're right.
However, using a Volkswagen as an example: you can tune it in many ways, and you still have a VW. But if you replace the engine with a Porsche Turbo Carrera engine, you no longer have a VW.

Just because your algo swaps adjacent elements, that does not make it a bubblesort. There are many non-bubble algo's which swap adjacent elements ---- I'm going to find some and post them for you.
*****


Title: Quicksort/ Bubblesort
Post by: na_th_an on June 11, 2004, 02:03:42 PM
Man, I was just clarifying my post, telling what I meant.
And I talk about what I've been taught. Just that.
Look for bubblesort in the internet. You'll find my algo.


Title: Quicksort/ Bubblesort
Post by: adosorken on June 11, 2004, 10:29:12 PM
na_th_an y moneo: you two should speak to each other in spanish to prevent miscommunication. :D


Title: Quicksort/ Bubblesort
Post by: LooseCaboose on June 12, 2004, 01:00:17 AM
na_th_an is right, for the simple fact that if you could code any sorting algorithm that used only a single loop (from 1..n) then you would have an O(n) average time algorithm and would now be very famous.

Moneo, in the worst case (data is reverse sorted), the algorithm you posted will do ((n - 1) * n) / 2, which is roughly O(n ^ 2), in the best case (data is already sorted) no swaps need to be done and the algorithm will complete in O(n) time.

Quote from: "dark_prevail"

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


When comparing algorithms like sorts, you usually compare by their mathmatical complexity rather than just benchmarking them. This (http://www.me.berkeley.edu/~e77/lecnotes/ch20/ch20.htm) page has some good info on the big O notation and even covers an analysis of bubblesort. Benchmarking is still worthwile for proving it works in real world applications though.

Interestingly, O(n ^ 2) sorts are still in use. In many applications that use sorts (The Linux kernel for example), quicksort or mergesort is used if there is a substantial amount of data, but if there is only a small amount (~ < 10 items) then the overhead isn't usually worth it and something like insertion sort is often used.


Title: Quicksort/ Bubblesort
Post by: Moneo on June 12, 2004, 01:45:50 AM
NATHAN,
I checked about 6 sort algorithms that I have (not from the Internet) and you're right. The only algo that swaps adjacent elements is the bubblesort. They all do swaps, but the elements are not necessarily adjacent.

LOOSE CABOOSE,
Thanks for the interesting sort information and calculations.

Most of the time here at the Forum we are trying to help someone in need of a sort routine. Many of us will agree that the bubblesort is pretty easy to understand and to get working. If we gave the poor guy a quicksort, not only would he not understand it, but if it had a bug in it, he would never find it and get very frustrated. So, the bubblesort is probably the slowest solution but it solves the problem for many first-timers getting into sort algorithms.
*****


Title: Quicksort/ Bubblesort
Post by: na_th_an on June 12, 2004, 02:40:20 PM
Well, the bubblesort algorithm DOES perform well with less elements to sort, and I also agree with Moneo: it's the best example for newbies to learn the basics of sorting. Once they've understood how it works, they can research on better (and more complex) algorithms.


Title: Quicksort/ Bubblesort
Post by: Moneo on June 12, 2004, 09:21:35 PM
Exactly --- thanks, Nathan.
*****


Title: Quicksort/ Bubblesort
Post by: zshzn on June 15, 2004, 03:18:58 AM
Anybody want to see a bogosort?  :D  'Tis where it sorts them randomly until the values end up as intended. Wheras the other sorting methods are very quick, this takes about 30 seconds to finish on my computer.

http://zshzn.250free.com/bogosort.txt

It is basic code saved in *.txt format.


Title: Quicksort/ Bubblesort
Post by: Oz on June 15, 2004, 09:18:11 AM
the only problem with that is if you have 99 indexes, you'll have to do another loop, so I don't think this would work in this particular case, but it is fairly fast.

Alex~