Ronald wrote:
>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?
If you look at the algorithm the way where it got his name
from, you'll see, that you don't have to iterate over the
*whole* list again and again.
0. 1. 2. 3. 4. 5. iteration
----------------------------
4 *6 *6 *6 *6 *6
6 4 *5 *5 *5 *5
1 5 4 *4 *4 *4
3 1 3 3 *3 *3
2 3 1 2 2 *2
5 2 2 1 1 1
* = already correctly sorted after iteration
You can see that the largest element of the unsorted list is
going up like a bubble in the water. After the first iteration
we know for sure, that the largest element is at the correct
position. The for the next iteration, we don't have to check
that again. With each loop, the list of unsorted elements get's
smaller. In the example above the list is sorted after the 3rd
iteration and no swaps happen during the 4th, so the algorithm
can stop.
>the classic bubble sort (as i understand it) works like this:
(pseudo code BASIC)
> snip
>if that makes any sense whatsoever... write me a tell me what
i just said!! :)
In your first example you are doing about twice as many
compares ((n-1)^2) in a worst-case scenario than in your second
one (n*(n-1)/2). And your second code will not recognize
already sorted lists and always need the worst-case number of
compares. (BTW: your 2nd code won't work, because you are
iterating in the wrong direction)
I'm not 100% sure, what is called *the* classic Bubble Sort,
but a combination of your two ideas result in exactly what I
would call the optimal Bubble Sort algorithm.
Look at my mail from 04:42 -0500 (EST). There you see the
optimized version, and you can see that the inner loop is
identical to the simple Bubble Sort and the outer loop is using
a swap check too. It's a bit complicated, so here is the
version I'm using in my code (simplier and NOT 100% optimal).
Bubble Sorting sorting a list with elements 1..N:
for i = N-1 downto 1
swapFlag = false
for j = 1 to i
if (y[j] > y[j+1]) then
swap(y[j], y[j+1])
swapFlag = true
end if
next j
if swapflag = false then exit
next i
The optimal solution mainly just replaces "swapflag" with a
value "k", that tells, where the last swap happened. Everything
above that is already correctly sorted. That way, it sometimes
can skip some outer iterations.
I hope, all this sorting stuff didn't went to much OT.
Have fun!
Thomas
________________________________________________________________
Keine verlorenen Lotto-Quittungen, keine vergessenen Gewinne mehr!
Beim WEB.DE Lottoservice: http://tippen2.web.de/?x=13
----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
