Subject: Re: [stella] Bubble Sort (Rodnay Zaks Version) From: Thomas Jentzsch <tjentzsch@xxxxxx> Date: Tue, 26 Mar 2002 15:46:16 +0100 |
Ronald wrote: >It appears that's how he stores the number of elements in his table - but, >as I understand it, this IS the classic bubble sort, and, if i may, how do >you know a list is sorted if you don't go thru it at least once w/o a swap? If you look at the algorithm the way where it got his name from, you'll see, that you don't have to iterate over the *whole* list again and again. 0. 1. 2. 3. 4. 5. iteration ---------------------------- 4 *6 *6 *6 *6 *6 6 4 *5 *5 *5 *5 1 5 4 *4 *4 *4 3 1 3 3 *3 *3 2 3 1 2 2 *2 5 2 2 1 1 1 * = already correctly sorted after iteration You can see that the largest element of the unsorted list is going up like a bubble in the water. After the first iteration we know for sure, that the largest element is at the correct position. The for the next iteration, we don't have to check that again. With each loop, the list of unsorted elements get's smaller. In the example above the list is sorted after the 3rd iteration and no swaps happen during the 4th, so the algorithm can stop. >the classic bubble sort (as i understand it) works like this: (pseudo code BASIC) > snip >if that makes any sense whatsoever... write me a tell me what i just said!! :) In your first example you are doing about twice as many compares ((n-1)^2) in a worst-case scenario than in your second one (n*(n-1)/2). And your second code will not recognize already sorted lists and always need the worst-case number of compares. (BTW: your 2nd code won't work, because you are iterating in the wrong direction) I'm not 100% sure, what is called *the* classic Bubble Sort, but a combination of your two ideas result in exactly what I would call the optimal Bubble Sort algorithm. Look at my mail from 04:42 -0500 (EST). There you see the optimized version, and you can see that the inner loop is identical to the simple Bubble Sort and the outer loop is using a swap check too. It's a bit complicated, so here is the version I'm using in my code (simplier and NOT 100% optimal). 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. I hope, all this sorting stuff didn't went to much OT. Have fun! Thomas ________________________________________________________________ Keine verlorenen Lotto-Quittungen, keine vergessenen Gewinne mehr! Beim WEB.DE Lottoservice: http://tippen2.web.de/?x=13 ---------------------------------------------------------------------------------------------- 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 (Rodnay Za, Ronald A. Laski, Jr. | Thread | Re: [stella] Bubble Sort (Rodnay Za, Chris Wilkson |
Re: [stella] Bubble Sort (Rodnay Za, Ronald A. Laski, Jr. | Date | Re: [stella] Bubble Sort, Andrew Davie |
Month |