Subject: Re: [stella] Bubble Sort (Rodnay Zaks Version) From: "Ronald A. Laski, Jr." <rlaski@xxxxxxxxxxx> Date: Tue, 26 Mar 2002 07:34:48 -0600 |
>This is the Rodnay Zaks Bubble Sort (if anybody cares! :)It appears that's how he stores the number of elements in his table - but, as I understand it, this IS the classic bubble sort, and, if i may, how do you know a list is sorted if you don't go thru it at least once w/o a swap?
I do! :-)
>Anyway, hope it helps... i'm not saying it's optimized or > anything, but here it is...
Hm, if I understand that correct, he stores the number of elements at the beginning of the list. And then he repeats going through the *whole* list until no more swaps happen.
Yes, that sorts, but that's no correct Bubble Sort. He needs about twice as many compares ((n-1)^2 vs n*(n-1)/2) compares as for a correct Bubble Sort implementation.
Sorting has always been a source of (in?)famous errors and misunderstandings, even the great R. Zaks failed. :-)
Have fun! Thomas
n = number of elements 10 swapflag = false 20 for i = 0 to n-1: rem or for i = 1 to n-1 to prevent an 'off-by-1' error' 30 if tablearray(i) > tablearray(i+1) then gosub SWAP 40 next i 50 if swapflag then 20 60 rem sorted..... 70 rem rest of pgm, blah blah blah..
20000 rem SWAP sub 20010 "Swap elements" 20020 swapflag = true 20030 return
---------------------------------------------------------------------------------------------- Archives (includes files) at http://www.biglist.com/lists/stella/archives/ Unsub & more at http://www.biglist.com/lists/stella/
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [stella] Bubble Sort (Rodnay Za, Thomas Jentzsch | Thread | Re: [stella] Bubble Sort (Rodnay Za, Thomas Jentzsch |
Re: Aw: Re: Aw: Aw: Re: [stella] Bu, Thomas Jentzsch | Date | Re: [stella] Bubble Sort (Rodnay Za, Thomas Jentzsch |
Month |