Simple Sort Routine

[Havie]

So, in Target Renegade I need to sort maybe 6-8 numbers from low to high. Any suggestions as to the quickest sort routine. Not necessarily looking for the shortest or most elegant but one that works the quickest.

My initial thoughts were the only one that I know - Bubble sort. It would work and probably be alright with the low number of numbers to sort but usually there is someone out there with a bigger/better brain than me that knows better. Over to you clever people...

[Jobbo]

Insertion sort is an easy and fast option if the order doesn't change very much from frame to frame.

Here's an article about c64 sprite multiplexing which explains one use case:

http://selmiak.bplaced.net/games/c64...e-Multiplexing

[pink^abyss]

Originally Posted by Havie

So, in Target Renegade I need to sort maybe 6-8 numbers from low to high. Any suggestions as to the quickest sort routine. Not necessarily looking for the shortest or most elegant but one that works the quickest.

My initial thoughts were the only one that I know - Bubble sort. It would work and probably be alright with the low number of numbers to sort but usually there is someone out there with a bigger/better brain than me that knows better. Over to you clever people...

Often Bubble sort with just a single iteration each frame is good enough. That was often done in C64 games. You may get short sort glitches but as there is a lot of coherence between frames in games its usually just fine..

[Photon]

The simplest sort is to find the lowest number in the list and output it to a new increasing pointer (marking up the found number to be skipped). The quickest sort depends on the size of dataset and the presence of "turtles" (high numbers near the start of the list). With very small datasets most sorts are equal in speed. Both Bubble Sort and Insertion Sort are applicable, Insertion Sort is probably the quickest simple sort here.

Sometimes even a sort is overkill. If the number of items is very small, you can call a subroutine for each dataset size, say Sort6, Sort7, Sort8, and in each you have a rolled out if-then-else which outputs the correct list.

You can also keep a sorted list at all times, and when a sort value changes, you immediately update the sorted list. This can be a sort for only the price of a few instructions to update the list.

[Havie]

Thanks all - food for thought. Will have a play around.

[sparhawk]

For a small number of items, sorting may even be an overkill and a loop is faster. Depends on your usecase. As always with "fastest" the best way is to time it and see what works best for your scenario as this is a moving target.

[roondar]

I agree that use case does matter here. For instance, if the order of items doesn't change much between calls to the sorting routine, Insertion Sort will likely be faster than most other algorithms.

In general, when it comes to simple sorting algorithms I tend to prefer Insertion Sort (both for it's high speed in partially sorted sets and because real world tests consistently show it to be faster than other simple sorts such as Bubble Sort in almost all cases). However, like others pointed out as well - if you have a very small number of items, a purpose built sort might be better.

[Havie]

Thanks guys - decided to just keep it simple as not many values and just find the lowest value in the list and put it at the top, then repeat etc. With a list of 5 objects it has to just do 4+3+2+1 loops. Even with 6 objects it will take only 15 loops. Obviously I was planning up to 8 objects but may only need maximum of 5?

Problem is my brain is scrambled and my code works sometimes and other times one number doubles. Can't for the life of me work out why sometimes the numbers sort properly from low to high and sometimes not? So thought I'd post it here and someone can spot my obvious error!

Thanks.

BitMap 0,320,256,5
InitCopList 0,44,256,5,8,32,0

BLITZ
CreateDisplay 0,0
Use BitMap 0

 ;z-order list
Dim z(8,2) ; z(shape,y coord)

z(1,1)=1:z(1,2)=270 ;player 1 in list

For n=2 To 5: z(n,1)=2: z(n,2)=Int(Rnd(500)): Next n
BitMapOutput 0:For n=1 To 5: Locate 1,n:Print z(n,1):Print" ":Print z(n,2): Next n

yy=1
For zz=1 To 4

    stored_y=z(zz,2): stored_shape=z(zz,1)

    Locate 0,10:Print "stored_y="::Print stored_y
    Locate 0,11: Print "stored_shape=":Print stored_shape
    VWait: DisplayBitMap 0,0

    For x =yy+1 To 5
      If z(x,2)<stored_y Then  stored_y=z(x,2): stored_shape= z(x,1):num=x
    Next x

    zt=z(yy,1): zs=z(yy,2)
    z(zz,1)=stored_shape: z(zz,2)=stored_y
    z(num,1)=zt:z(num,2)=zs

     yy+1

Next zz

Use BitMapOutput 0:For n=1 To 5: Locate 10,n:Print z(n,1):Print" ":Print z(n,2): Next n

VWait
DisplayBitMap 0,0

  While RawStatus(69)=0
  Wend

End

[Havie]

Found my bug.

The issue with the code is that I use num to store the number on the list of the lowest term but after each iteration of the list, I then start on the next term down as the term above has been filled with the lowest number. If the term I start on is already the lowest then the IF statement is never true and num is never set and is left at whatever it was at the end of the last iteration so the next lowest value is put in the wrong place.

The solution is to set num to yy (which is the first term on the list) so if it is the lowest value on the list, num is correctly pointing at it. If it isn't the lowest term the the IF statement will be true and num will set to this value.

Simples!

I'm not sure but I think this is an insertion sort as I find the lowest number and insert in the correct place in the list.

Phew!!! Now to add the code to the game and z-ordering should be working.

[Havie]

My z ordering routine wasn't working so re-visited my code (after a bit of Googling) and not only does it now work properly but it's much shorter!

i=1

While i<length of list
  j=i

  While j>1 AND z(j-1)>z(j)
    a=z(j-1):b=z(j):z(j-1)=b:z(j)=a
    j-1
  Wend
  i+1
Wend

[DanScott]

i=1

While i<length of list
  j=i

  While j>1 AND z(j-1)>z(j)
    a=z(j-1):z(j-1)=z(j):z(j)=a
    j-1
  Wend
  i+1
Wend

shorter

[Nightshft]

Looks like this is one iteration of a bubblesort. From what you tell it works well enough for your program.

I just tried around and expanded it to a complete sort routine here:

n.w=#size  ;size of array

Repeat
  swapped.w=0
  For i.w=0 To n-1
    If myArray(i-1)>myArray(i)
      temp.w = myArray(i-1)
      myArray(i-1) = myArray(i)
      myArray(i)   = temp
      swapped=-1
    EndIf
  Next
  n-1
Until swapped=0

Addendum:
Note that amiblitz also has a sort command built in. Seems to work fine for 1-dimensional arrays. No idea if it works for 2-dimensional arrays, or how fast it is.

[Retro1234]

Create a sort list as you display them, that is used for the next display?