Qbasicnews.com
April 05, 2020, 12:06:59 AM
 Pages: 1 [2]
 Author Topic: Quicksort/ Bubblesort  (Read 6812 times)
na_th_an
*/-\*

Posts: 8244

 « Reply #15 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).
 Logged

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

Posts: 1971

 « Reply #16 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.
*****
 Logged
na_th_an
*/-\*

Posts: 8244

 « Reply #17 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%.
 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 #18 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.
 Logged
Moneo
Na_th_an

Posts: 1971

 « Reply #19 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.
*****
 Logged
na_th_an
*/-\*

Posts: 8244

 « Reply #20 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.
 Logged

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

Posts: 3655

 « Reply #21 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.
 Logged

I'd knock on wood, but my desk is particle board.
LooseCaboose
I hold this place together

Posts: 981

 « Reply #22 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 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.
 Logged

esus saves.... Passes to Moses, shoots, he scores!
Moneo
Na_th_an

Posts: 1971

 « Reply #23 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.
*****
 Logged
na_th_an
*/-\*

Posts: 8244

 « Reply #24 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.
 Logged

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

Posts: 1971

 « Reply #25 on: June 12, 2004, 09:21:35 PM »

Exactly --- thanks, Nathan.
*****
 Logged
zshzn
Member

Posts: 89

 « Reply #26 on: June 15, 2004, 03:18:58 AM »

Anybody want to see a bogosort?    '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.
 Logged
Oz
I hold this place together

Posts: 923

 « Reply #27 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~
 Logged
 Pages: 1 [2]