3/25/2002 9:18:01 AM, cybergoth@xxxxxxxx wrote:
>> 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?
Couldn't you just insert the object at the beginning of the list
if it's entering at the top of the screen, and insert it at the end of
the list if it's entering at the bottom of the screen?
Taking that to a more generic case, you could have a separate
insert routine that steps through the list and inserts a new object
in the appropriate place. That can't take more than n time.
That almost changes the paradigm from a sorted array to a
priority queue, which when you think about it is what your 2600
display kernel really is...
Julian Squires <tek@xxxxxxx> wrote:
>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.
Careful here - Classic sorting algorithms are usually defined as
speed being the number of swaps required. In tightly timed
6502 assembly language, the comparisons and looping take a
quite significant amount of time already. In the example
of 7, 1, 2, 3, 4, 5, 6, you require n^2 comparisons (actually
(n-1)^2) to get the 7 to the end of the list.
----------------------------------------------------------------------------------------------
Archives (includes files) at http://www.biglist.com/lists/stella/archives/
Unsub & more at http://www.biglist.com/lists/stella/
