Re: [stella] Bubble Sort

Subject: Re: [stella] Bubble Sort
From: Thomas Jentzsch <tjentzsch@xxxxxx>
Date: Tue, 26 Mar 2002 10:45:48 +0100
Tim wrote:
>The compare is the other way around! You have
>to change the branch condition.

Yup, my fault. No "magic" involved. :-)

Manuel wrote:
>Uhm... won't work?
>The one I posted does a perfect job, unlike yours. See 
>the demos I attached :-)

I'm still 100% sure that this algorithm will NOT work.

Example: 3 2 1
- tempVar1 starts with 1 (#MAXOBJECTS-2)
- after the first outer loop you get: 1 3 2
- then tempVar1 is decreased to 0
- in the next (and last) outer loop, the inner loop will only 
compare 1 and 3, 2 will not be compared again and therefore 
should be already correctly sorted, and that's not the case. 

Make your demo a little bit slower, then it might be easier to 
spot the sorting errors. And with slower movement, it's also 
much easier to evaluate flicker.

BTW: This is a simple Bubble Sort (64'er 4/85):
  for i = N-1 downto 1
    for j = 1 to i 
      if (y[j] > y[j+1]) 
        swap(y[j], y[j+1]) 

And here is the optimized Bubble Sort (according to Knuth):
  k = N
    i = k-1
    k = 0 
    for j = 1 to i 
      if (y[j] > y[j+1]) 
        swap(y[j], y[j+1]) 
        k = j
  until k = 0

Have fun!	

Archives (includes files) at
Unsub & more at

Current Thread