Re: [stella] Bubble Sort (Rodnay Zaks Version)

Subject: Re: [stella] Bubble Sort (Rodnay Zaks Version)
From: Thomas Jentzsch <tjentzsch@xxxxxx>
Date: Tue, 26 Mar 2002 15:46:16 +0100
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!	
Keine verlorenen Lotto-Quittungen, keine vergessenen Gewinne mehr! 
Beim WEB.DE Lottoservice:

Archives (includes files) at
Unsub & more at

Current Thread