Re: Aw: Re: [stella] Sorting Algorithms.

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