## Re: [stella] Bubble Sort

 Subject: Re: [stella] Bubble Sort From: Thomas Jentzsch Date: Tue, 26 Mar 2002 18:33:39 +0100
```Andrew wrote:
>A = (min 1, ave N- sqrt( piN/2 + O(1), max N);  (10)
>B = (min 0, ave 1/4(N^2 - N), max 1/2(N^2 - N)); (11)
>C = (min N - 1, ave 1/2( N^2 - NlnN - (lambda + ln2 -1) N) + O
(sqrt(n), max 1/2(N^2-N)). (12)

I don't have the book, but combined with Julian's MIX code I
get:
A = outer loop (general overhead)
B = swapping elements
C = inner loop (compares)

>In each case the minimum occurs when the input is already in
>order, and the maximum occurs when it is in reverse order;  so
>the MIX running time is
> 8A + 7B + 8C + 1 = (min 8N + 1, ave 5.75N^2 + O(N log N), max
> 7.5N^2 + 0.5N + 1).

For an already *nearly sorted* (and also rather small) list,
you will be very close to the minimum values. So the MIX
running time will be very close to c*N (c = some constant
value) and therefore complexity will be about O(N), right?

Does any other suitable algorithm provide such a good minimum?

Have fun!
Thomas

----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/

```