When I learned (and promptly forgot) all of this years ago, the "classic"
bubble sort was the simple version. You always sort throught the entire
list until there are no more swaps. The "better" bubble sort would
recognize that the last n elements were already sorted, and would shorten
the length of the sort list as needed. The version that Thomas includes
below, using "k" for the last swap position, is an optimized form of the
better bubble sort alogorithm, but I don't remember what it's called.
I just remember seeing it before, in that evil, evil class.
-Chris
On Tue, 26 Mar 2002, Thomas Jentzsch wrote:
> 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.
----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
