Re: [stella] Bubble Sort

Subject: Re: [stella] Bubble Sort
From: Thomas Jentzsch <tjentzsch@xxxxxx>
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/


Current Thread