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

Subject: Aw: Re: Aw: Re: [stella] Sorting Algorithms.
From: cybergoth@xxxxxxxx
Date: Mon, 25 Mar 2002 15:18:01 +0100 (MET)
Hi Julian!

> 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.

The number of swaps is only n, agreed. But inserting the 7
at the beginning would only move it one spot per iteration,
so you'd have to do both loops completely, with n^2
compares at least, right?

That's what I call worst case :-)

> > 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. 

Thanks a lot for these explanations! I really had no clue at all,
what even the idea behind Quicksort was. All I knew was that
something exists by this name :-)

> You should look at Knuth's Sorting and Searching (TAOCP volume 3).

Is this document online somewhere?

Otherwise...

> 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.

...I'd like to ask you, if you probably could type in both the bubble and
the insertion sort for me?

Greetings,
     Manuel


-----------------------------------------------------------------------
Riester-Rente - Kassieren Sie das Geld vom Staat:
Zum Förderungsrechner! http://www.arcor.de/home/redir.php/riesterrente
-----------------------------------------------------------------------

----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/


Current Thread