Subject: Re: Aw: Re: Aw: Re: [stella] Sorting Algorithms. From: Erik Mooney <erik@xxxxxxxxxx> Date: Mon, 25 Mar 2002 11:52:19 -0500 |
3/25/2002 11:09:16 AM, Greg Miller <gmiller@xxxxxxxxxxxxxxxxx> wrote: >> 3/25/2002 9:18:01 AM, cybergoth@xxxxxxxx wrote: >> Careful here - Classic sorting algorithms are usually defined as >> speed being the number of swaps required. In tightly timed >> 6502 assembly language, the comparisons and looping take a >> quite significant amount of time already. In the example >> of 7, 1, 2, 3, 4, 5, 6, you require n^2 comparisons (actually >> (n-1)^2) to get the 7 to the end of the list. > > >Actually, the classic bubble sort implementation requires 6 comparisons >to get the 7 into the proper place, then one more pass to notice that >the data is now in sorted order. You compare 7 to 1 and swap it, then 7 >to 2, then 7 to 3, etc. Actually, you're right. But in the reverse case - 2, 3, 4, 5, 6, 7, 1 - it would take n^2 comparisons although only n swaps. ---------------------------------------------------------------------------------------------- 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: Aw: Re: Aw: Re: [stella] Sortin, Greg Miller | Thread | Re: Aw: Re: Aw: Re: [stella] Sortin, Adam Wozniak |
Aw: Re: Aw: Re: Aw: Re: [stella] So, cybergoth | Date | Aw: Re: Aw: Re: [stella] Sorting Al, Thomas Jentzsch |
Month |