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
Quick-Sort works, since I've no clue at all about this one...
> >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 :-)

Riester-Rente - Kassieren Sie das Geld vom Staat:
Zum Förderungsrechner!

Archives (includes files) at
Unsub & more at

Current Thread