At 11:30 AM 3/26/2002 +0100, you wrote:
>This is the Rodnay Zaks Bubble Sort (if anybody cares! :)
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
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?
the classic bubble sort (as i understand it) works like this: (pseudo code
BASIC)
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
pardon my crudeness in this pseudo code, but isn't that the classic
description of a bubble sort? going thru the list 1 step at a time,
comparing each element to the next one? when no data swaps take place, the
list is sorted?
also, compare this, if you don't have a worst case list, your sort gets
done quicker than any other type of similar 'bubble sort' that requires 2
loops... like the 'straightforward' approach i believe you called it, if
the sort requires 2 loops, then they'll finish when they're done,
regardless of whether or not any swaps took place right? (as in this bit of
BASIC pseudo code again)
n = number of elements
i = top of the list or current element to be searched
j= the 'rest' of the list to compare to see if it belongs in the 'i'
position of the array.
10 for i = 0 (or 1 as before) to n-1 (i think this could be just 'n' but
that causes at least one more extra compare)
20 for j = i+1 to n
30 if tablearray(i) > tablearray(j) then gosub SWAP (but no swapflag
necessary in this case)
40 next j: next i
50 rem - list is sorted when the loops roll out, doing more compares than
necessary if the list isn't in it's worst case scenario, whereas the
'classic' bubble sort would be done at the next loop for a swap check
(which shouldn't happen).
if that makes any sense whatsoever... write me a tell me what i just said!! :)
Ron
----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
