29 August 2021, 11:42 | #1 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
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... |
29 August 2021, 17:04 | #2 |
Registered User
Join Date: Jun 2020
Location: Druidia
Posts: 389
|
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 |
29 August 2021, 17:11 | #3 | |
Registered User
Join Date: Aug 2018
Location: Untergrund/Germany
Posts: 410
|
Quote:
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.. |
|
29 August 2021, 20:43 | #4 |
Moderator
Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 5,690
|
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. |
30 August 2021, 22:39 | #5 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
Thanks all - food for thought. Will have a play around.
|
31 August 2021, 12:08 | #6 |
Registered User
Join Date: Sep 2019
Location: Essen/Germany
Age: 55
Posts: 463
|
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.
|
31 August 2021, 13:29 | #7 |
Registered User
Join Date: Jul 2015
Location: The Netherlands
Posts: 3,438
|
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. |
31 August 2021, 21:26 | #8 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
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 |
01 September 2021, 21:51 | #9 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
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. |
21 November 2021, 23:24 | #10 |
Registered User
Join Date: Mar 2012
Location: UK
Posts: 1,895
|
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 |
22 November 2021, 00:00 | #11 |
Lemon. / Core Design
Join Date: Mar 2016
Location: Tier 5
Posts: 1,213
|
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 |
22 November 2021, 17:16 | #12 |
Registered User
Join Date: Mar 2018
Location: Austria
Posts: 617
|
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 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 17:35. |
22 November 2021, 19:34 | #13 |
Phone Homer
Join Date: Jun 2006
Location: 5150
Posts: 5,827
|
Create a sort list as you display them, that is used for the next display?
|
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 21:40 |
Simple and ugly text wrapping routine | rockersuke | Coders. AMOS | 7 | 21 November 2014 22:31 |
Anyone help me sort my CF card? | Kola | Amiga scene | 73 | 01 November 2014 08:49 |
Sort and Search | CdrJameson | AMR suggestions and feedback | 1 | 14 March 2007 21:24 |
Looking for some routine code | Amiga1992 | Coders. General | 4 | 17 December 2003 23:51 |
|
|