Re: [stella] Bubble Sort

Subject: Re: [stella] Bubble Sort
From: Thomas Jentzsch <tjentzsch@xxxxxx>
Date: Tue, 26 Mar 2002 10:41:03 +0100
Tim wrote:
>How about this ? Sometimes it is a good idea
>to optimize the algorithm. Sorry, untested
>and unfinished but you get the idea..

Yes, this is pointing to another simple sorting idea. The 
correct algorithm is called "Straight Selection". 

Here is some pseudocode:
  for i = N downto 2
    k = i
    for j = 1 to i-1
      if (y[j] > y[k]) k = j
    swap(y[i], y[k])

Inner and outer loop are going in opposite directions again.

The complexity is as bad as Bubble Sort (O(n^2)), but the 
implementation is often easier and faster. What you loose, is 
Bubble Sort's very good performance with nearly sorted lists 
and the chance to recognize when the list is sorted.

Have fun!	

Archives (includes files) at
Unsub & more at

Current Thread