Subject: Re: Aw: Re: [stella] Sorting Algorithms. From: Julian Squires <tek@xxxxxxx> Date: Mon, 25 Mar 2002 10:15:18 -0330 |
On Mon, Mar 25, 2002 at 02:26:57PM +0100, cybergoth@xxxxxxxx wrote: > Well, in this example the zero would be sorted to the beginning > in one iteration, but: > > Having 1,2,3,4,5,6 and adding the 7 at the _beginning_, would > be worst case, or? And that can happen any time, I think. No, worst case is sorting 7,6,5,4,3,2,1. Even with 7 at the beginning, there will only be n swaps if the rest of the list is sorted. The worst case involved n^2 swaps. > I'd be interested in that too. Especially I'd be interested in how > Quick-Sort works, since I've no clue at all about this one... Quicksort is probably not suitable for this application. Implementation is easy if you use recursion, but with the limited stack space available, you'd want to implement it iteratively which is far more complex than a simple sort, without giving you any real gains. Quicksort works best on unsorted lists, so it would probably perform very poorly in your general case. In fact, many quicksort algorithms randomize the list before sorting it... You should look at Knuth's Sorting and Searching (TAOCP volume 3). Thanks to his wise decision to use assembly language to demonstrate the algorithms, you can see what an implementation of quicksort would be like in a language similar to 6502 assembly. It is about 63 lines of ``MIXAL'', and uses a stack. The bubble sort implementation is 16 lines and appears to use only one extra word of storage. On the other hand, insertion sort is only 12 lines, uses no additional storage, and might perform slightly better than bubble sort in your cases. -- -/ |/| Julian Squires <tek@xxxxxxx> /- ---------------------------------------------------------------------------------------------- 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 -> |
---|---|---|
Aw: Re: [stella] Sorting Algorithms, cybergoth | Thread | Re: Aw: Re: [stella] Sorting Algori, Thomas Jentzsch |
Aw: Re: [stella] Sorting Algorithms, cybergoth | Date | Aw: Re: Aw: Re: [stella] Sorting Al, cybergoth |
Month |