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

 Subject: Aw: Re: [stella] Sorting Algorithms. From: cybergoth@xxxxxxxx Date: Mon, 25 Mar 2002 14:26:57 +0100 (MET)
```Hi Thomas!

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

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.

But I've to think some more about it, maybe I'm just on
a very wrong path now :-)

Hm... to always have stuff inserted at one side, you'd
have to shift all indexes together, once an object
disappears, right? Hm.... hm... might work.

Then the max number of (outerloop) iterations = number
of objects inserted, yes?

> Perhaps we should search the Web for some theorie about sorting
> and partially sorted lists. :-)

I'd be interested in that too. Especially I'd be interested in how

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

Ok, if you only randomize Xs and have other rules for generating
Ys, then you're getting away with it :-)

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/

```