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 |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [stella] Bubble Sort, Thomas Jentzsch | Thread | [stella] Bubble Sort II, cybergoth |
Re: [stella] Bubble Sort, Julian Squires | Date | Re: [stella] Bubble Sort, Thomas Jentzsch |
Month |