Re: [stella] Sorting Algorithms.

Subject: Re: [stella] Sorting Algorithms.
From: "Andrew Davie" <adavie@xxxxxxxxxxx>
Date: Tue, 26 Mar 2002 00:39:26 +1100
> Perhaps we should search the Web for some theorie about sorting
> and partially sorted lists. :-)


Get yourself a copy of "The Art of Computer Programming" by Donald Knuth.
The whole of volume 3 is on Sorting and Searching.

If it's not in Knuth, it's not worth knowing.

Cheers
A
-
Andrew Davie - adavie@xxxxxxxxxxx
TwoHeaded Software - www.2headed.com


----- Original Message -----
From: "Thomas Jentzsch" <tjentzsch@xxxxxx>
To: <stella@xxxxxxxxxxx>
Sent: Monday, March 25, 2002 11:59 PM
Subject: Re: [stella] Sorting Algorithms.


> Manuel wrote:
> >Well, unfortunately, I'd have objects appear/disappear any
> given time,
> >any place. So a new enemy flying into the scene from top or
> bottom,
> >might (depending on the sort order) result in a worst-case
> >Bubble Sort, from one frame to another!
>
> If you have e.g. 1,2,3,4,5,6 and add 0 and 7 to the end, the
> list is still sorted after one single iteration when the inner
> loop is running backwards. I can't think of real worst-case
> scenarios.
>
> Perhaps we should search the Web for some theorie about sorting
> and partially sorted lists. :-)
>
> The stop-overhead is very marginal, because it's only checked
> in the outer loop.
>
>
> >Hm... even when doing Bubble Sort, I'd
> >probably have to sort only links, otherwise
> >I'd have to swap
> >Y-Pos/X-Pos/Size/Color/Y-Movment & X-Movement
> >values on every occuring swap :-)
>
> Yes, that's a disadvantage.
>
>
> >Well, nothing prevents me from using the links only
> >temporary for the sorting, then doing all necessary
> >swaps _once_ :-)
>
> Agreed.
>
>
> >BTW: Wouldn't you have to support worst-case sort too,
> >when switching to the next level?
>
> Depends on how you generate the random positions and/or if you
> can handle worst-case in special situations.
>
> Have fun!
> Thomas
>
>
>
>
>
>
> --------------------------------------------------------------------------
--------------------
> Archives (includes files) at http://www.biglist.com/lists/stella/archives/
> Unsub & more at http://www.biglist.com/lists/stella/
>
>

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


Current Thread