English Amiga Board Simple Sort Routine
 Register Amiga FAQ Rules & Help Members List  /  Moderators List Today's Posts Mark Forums Read

 29 August 2021, 12:42 #1 Havie Registered User   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...
 29 August 2021, 18:04 #2 Jobbo Registered User   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
29 August 2021, 18:11   #3
pink^abyss
Registered User

Join Date: Aug 2018
Location: Untergrund/Germany
Posts: 321
Quote:
 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..

 29 August 2021, 21:43 #4 Photon Moderator   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.
 30 August 2021, 23:39 #5 Havie Registered User   Join Date: Mar 2012 Location: UK Posts: 1,376 Thanks all - food for thought. Will have a play around.
 31 August 2021, 13:08 #6 sparhawk Registered User   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.
 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.
 31 August 2021, 22:26 #8 Havie Registered User   Join Date: Mar 2012 Location: UK Posts: 1,376 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)
 01 September 2021, 22:51 #9 Havie Registered User   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.
 22 November 2021, 00:24 #10 Havie Registered User   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 i1 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, 01:00 #11 DanScott Lemon. / Core Design   Join Date: Mar 2016 Location: Tier 5 Posts: 1,061 Code: ```i=1 While i1 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
 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.
 22 November 2021, 20:34 #13 Retro1234 Boo   Join Date: Jun 2006 Location: 5150 Posts: 4,972 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)

 Similar Threads Thread Thread Starter Forum Replies Last Post Tuckernem support.Hardware 1 16 April 2017 22:40 rockersuke Coders. AMOS 7 21 November 2014 23:31 Kola Amiga scene 73 01 November 2014 09:49 CdrJameson AMR suggestions and feedback 1 14 March 2007 22:24 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home News Main     Amiga scene     Retrogaming General Discussion     Nostalgia & memories Support     New to Emulation or Amiga scene         Member Introductions     support.WinUAE     support.WinFellow     support.OtherUAE     support.FS-UAE         project.AmigaLive     support.Hardware         Hardware mods         Hardware pics     support.Games     support.Demos     support.Apps     support.Amiga Forever     support.Amix     support.AmigaOS     support.Other Requests     request.UAE Wishlist     request.Old Rare Games     request.Demos     request.Apps     request.Modules     request.Music     request.Other     Looking for a game name ?     Games images which need to be WHDified abime.net - Hall Of Light     HOL news     HOL suggestions and feedback     HOL data problems     HOL contributions abime.net - Amiga Magazine Rack     AMR news     AMR suggestions and feedback     AMR data problems     AMR contributions abime.net - Home Projects     project.Amiga Lore     project.EAB     project.IRC     project.Mods Jukebox     project.Wiki abime.net - Hosted Projects     project.aGTW     project.APoV     project.ClassicWB     project.Jambo!     project.Green Amiga Alien GUIDES     project.Maptapper     project.Sprites     project.WinUAE - Kaillera Other Projects     project.Amiga Demo DVD     project.Amiga Game Factory     project.CARE     project.Amiga File Server     project.CD32 Conversion     project.Game Cover Art         GCA.Feedback and Suggestions         GCA.Work in Progress         GCA.Cover Requests         GCA.Usefull Programs         GCA.Helpdesk     project.KGLoad     project.MAGE     project.Missing Full Shareware Games     project.SPS (was CAPS)     project.TOSEC (amiga only)     project.WHDLoad         project.Killergorilla's WHD packs Misc     Amiga websites reviews     MarketPlace         Swapshop     Kinky Amiga Stuff     Collections     EAB's competition Coders     Coders. General         Coders. Releases         Coders. Tutorials     Coders. Asm / Hardware     Coders. System         Coders. Scripting         Coders. Nextgen     Coders. Language         Coders. C/C++         Coders. AMOS         Coders. Blitz Basic     Coders. Contest         Coders. Entries Creation     Graphics         Graphics. Work In Progress         Graphics. Finished Work         Graphics. Tutorials     Music         Music. Work In Progress         Music. Finished Work         Music. Tutorials

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

 -- EAB3 skin ---- EAB2 skin ---- Mobile skin Archive - Top