Jump to content


Photo

Basic Array Functions


  • Please log in to reply
3 replies to this topic

#1 Desert Dog

Desert Dog

    GMC Member

  • GMC Elder
  • 6409 posts
  • Version:Unknown

Posted 07 January 2013 - 08:33 AM

----------------- The Intro ------------------

I've noticed a few questions in the Q&A forum lately on sorting an array. I only know the bubblesort 'off hand', so I give this to them, but this is hardly the best.

Searching on the site, there are some nice sorting functions, but it seems that all of them use functions like variable_local_array_get() or such.. these functions no longer exist in GM-S.

Actually, there is no way to pass an array to a script in GM. So these functions simply work to manipulate a 'myArray'.. it's up to you to replace it with your own array name.

So I've implemented some of the standard sorting algorithm's into GML.. and I'm posting it here, so that I can just send people here.

Here is what I've got.

-------------- The Code --------------

shuffle_array( size );
Spoiler


array_in_order( size )
Spoiler


simple_bubblesort - - Note.. this is not optimal, and is only included as it's simple, and easy to understand
Spoiler


bubblesort( size ) -- optimised ( should be )
Spoiler


bogosort -- Just a bit of fun. I saw this on wikipedia, and had to write it. (don't actually use it!)
Spoiler


insertion_sort( size )
Spoiler


quicksort( size ) -- quicksort is usually a recursive algorithm. However, GM-S does have a problem with recursion.. it can only go down to a depth of 32. Also, as a general rule recursion should be avoided in GM anyways. So here is an iterative implementation that I found, and implemented in GML..
Spoiler


mergesort() - a very fast sorting algorithm, which rivals quicksort..
Spoiler


heapsort() - again, a very quick sorting algorithm. Usually recursive, this script is the bottom-up implementation, which avoid that recursive behavior.
Spoiler



--------------The Rambling --------------

I haven't done any serious speed tests..( no numbers). But I quickly tried to sort a large array ( 1000 ).. it took the bubblesort's a second or so.. the insertion_sort was marginally faster. The quicksort() was very fast! Again, no actual numbers, but I'd estimate it's at least 4 times faster than the the next fastest. Make that more like 10-20 times faster. With an array sized 3000+, there is no comparison between bubblesort, and quicksort. Phew!

What one should you use? Well, whichever one suits you. If you have a small array, just use a bubblesort.. it'll be fine. If you want to be a bit more adventurous, I believe insertion_sort is overall generally better than bubblesort.

If you have a large array, definitely go for the quicksort. If you have a VERY large array, use bogosort()
  • 3
HTML5 games for mobile:
HexDogs Bugz Burn! Captain George Golfing Block Memory

Games for Androids
*NEW* Word Dog - Published by Dangerous_Dave


Code: General Array Functions - GM-S friendly. sorting, shuffling. Includes a quicksort.
Use the quicksort to sort ds_lists 10-18 times faster than ds_list_sort()!

#2 Desert Dog

Desert Dog

    GMC Member

  • GMC Elder
  • 6409 posts
  • Version:Unknown

Posted 13 January 2013 - 03:39 AM

Topic's been updated with the very fast mergesort(), and heapsort() algorithm.

At the suggestion of Dangerous_Dave.. the quicksort algorithm can be modified slightly, to take a reference to a ds_list.. which it will then sort.
Here's the script for that:
ds_quicksort()
Spoiler


This can sort a random ds_list of 5000, about 10, to 18 times faster than the built-in ds_list_sort()!
Please see wikipedia article on quicksort() to see the disadvantages of the quicksort algorithm, and only use this instead of ds_list_sort() where appropriate... ds_list_sort() would be faster for almost sorted/already sorted lists.
  • 0
HTML5 games for mobile:
HexDogs Bugz Burn! Captain George Golfing Block Memory

Games for Androids
*NEW* Word Dog - Published by Dangerous_Dave


Code: General Array Functions - GM-S friendly. sorting, shuffling. Includes a quicksort.
Use the quicksort to sort ds_lists 10-18 times faster than ds_list_sort()!

#3 Ruub

Ruub

    Finn The Human

  • GMC Member
  • 762 posts
  • Version:GM:Studio

Posted 29 April 2015 - 12:14 PM

sick.


  • 0

#4 Paolo Mazzon

Paolo Mazzon

    Has Too Much Time

  • GMC Member
  • 811 posts
  • Version:GM:Studio

Posted 17 May 2015 - 05:23 PM

These are some noice scripts, but if you needed to sort and shuffle and stuff, shouldn't you be using ds_lists?


  • 0