English Amiga Board


Go Back   English Amiga Board > Coders > Coders. Language > Coders. Blitz Basic

 
 
Thread Tools
Old 29 August 2021, 12:42   #1
Havie
Registered User
Havie's Avatar
 
Join Date: Mar 2012
Location: UK
Posts: 1,376
Simple Sort Routine

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...
Havie is offline  
Old 29 August 2021, 18:04   #2
Jobbo
Registered User

Jobbo's Avatar
 
Join Date: Jun 2020
Location: Druidia
Posts: 233
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
Jobbo is offline  
Old 29 August 2021, 18:11   #3
pink^abyss
Registered User
 
Join Date: Aug 2018
Location: Untergrund/Germany
Posts: 321
Quote:
Originally Posted by Havie View Post
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..
pink^abyss is offline  
Old 29 August 2021, 21:43   #4
Photon
Moderator

Photon's Avatar
 
Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 5,153
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.
Photon is offline  
Old 30 August 2021, 23:39   #5
Havie
Registered User
Havie's Avatar
 
Join Date: Mar 2012
Location: UK
Posts: 1,376
Thanks all - food for thought. Will have a play around.
Havie is offline  
Old 31 August 2021, 13:08   #6
sparhawk
Registered User

sparhawk's Avatar
 
Join Date: Sep 2019
Location: Essen/Germany
Age: 53
Posts: 459
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.
sparhawk is offline  
Old 31 August 2021, 14:29   #7
roondar
Registered User

 
Join Date: Jul 2015
Location: The Netherlands
Posts: 3,051
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.
roondar is offline  
Old 31 August 2021, 22:26   #8
Havie
Registered User
Havie's Avatar
 
Join Date: Mar 2012
Location: UK
Posts: 1,376
Post

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.

Code:
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 is offline  
Old 01 September 2021, 22:51   #9
Havie
Registered User
Havie's Avatar
 
Join Date: Mar 2012
Location: UK
Posts: 1,376
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 is offline  
Old 22 November 2021, 00:24   #10
Havie
Registered User
Havie's Avatar
 
Join Date: Mar 2012
Location: UK
Posts: 1,376
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!

Code:
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
Havie is offline  
Old 22 November 2021, 01:00   #11
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Tier 5
Posts: 1,061
Code:
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
DanScott is offline  
Old 22 November 2021, 18:16   #12
Nightshft
Registered User

 
Join Date: Mar 2018
Location: Austria
Posts: 501
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:

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

Last edited by Nightshft; 22 November 2021 at 18:35.
Nightshft is offline  
Old 22 November 2021, 20:34   #13
Retro1234
Boo

Retro1234's Avatar
 
Join Date: Jun 2006
Location: 5150
Posts: 4,972
Create a sort list as you display them, that is used for the next display?
Retro1234 is offline  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Can someone sort my cf card Tuckernem support.Hardware 1 16 April 2017 22:40
Simple and ugly text wrapping routine rockersuke Coders. AMOS 7 21 November 2014 23:31
Anyone help me sort my CF card? Kola Amiga scene 73 01 November 2014 09:49
Sort and Search CdrJameson AMR suggestions and feedback 1 14 March 2007 22:24
Looking for some routine code Akira Coders. General 4 18 December 2003 00:51

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 23:14.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, vBulletin Solutions Inc.
Page generated in 0.08260 seconds with 15 queries