Lesson 12: qSort

I needed to sort an array recently and I realised that I needed to use qSort, but not ever having used it before, I was initially quite confused until I worked out how it works. So I thought I would add my ever popular human-definition of what’s going on try to put it in simple terms.

So when we have an array like #(1,5,3,2,4) we can easily use the sort() function to sort this into an array #(1,2,3,4,5), simple. Ok but what if we wanted to sort an array of point2 values….

vals = #([10,10],[5,5],[4,4],[2,2],[1,1],[3,3])

A practical use of this might be when you are conducting some hit testing on an image and you want to see which point is closest to [0,0]. If we try to use the sort() function this happens…

sort #([10,10],[5,5],[4,4],[2,2],[1,1],[3,3])
 -- No "">"" function for [5,5]

And this is because the sort function is very simple, it is simply going through each item in the array and checking to see if it is bigger than each item in the sorted array and when it finds it’s place in the array it leaves it there. So with values like point2 values it doesn’t know how to compare them. This is why we can use qSort.

qsort <array> <function>

qSort has two arguments, first is the array we want to sort, next is the function, this is a custom-defined function that we write to sort our array.

So lets try sort our array into distance from [0,0]

fn myqSortFunction v1 v2 =
 (
 local d = distance [0,0] v1
 local dd = distance [0,0] v2
case of
 (
 (d < dd) : -1 (d > dd) : 1
 default: 0
 )
 )
vals = #([10,10],[5,5],[4,4],[2,2],[1,1],[3,3])
 qSort vals myqSortFunction
 vals

This returns…

#([1,1], [2,2], [3,3], [4,4], [5,5], [10,10])

Ok so lets break this all down, you might be confused as our myqSortFunction has two parameters yet we aren’t passing any arguments when we call qSort… This is because qSort is passing pairs of arguments to the myqSortFunction, we then tell it what to do with these values based on the return value of this function. There are 3 values that qSort expects to get back from the function, -1, 1, 0…. -1 means the v1 value needs to go before v2 value in the array, it’s important to not think of this as v1 is smaller than v2, as we are defining the rules of the sort, so it’s not necessarily that it’s smaller just that it needs to go before.

For instance if we were to switch -1 and +1 we’d get the array sorted into furthest distance from [0,0].

fn myqSortFunction v1 v2 =
 (
 local d = distance [0,0] v1
 local dd = distance [0,0] v2
case of
 (
 (d > dd) : -1
 (d < dd) : 1
 default: 0
 )
 )
vals = #([10,10],[5,5],[4,4],[2,2],[1,1],[3,3])
 qSort vals myqSortFunction
 vals

returns….

#([10,10], [5,5], [4,4], [3,3], [2,2], [1,1])

So it’s important to realise we are putting things in our own order, based on our rule. The ‘default: 0’ is required for when it’s sorting the first value and it doesn’t have anywhere to move it.

Our function simple looks at the distance from [0,0] to both the v1 value and the v2 value and by comparing which is bigger we know where these values need to go in an array in comparison to each other.

Optional parameters for qSort are… [start:] [end:] [user-defined key args passed to function]

So we can define where in the array we want to sort…. (using our first function)

qSort vals myqSortFunction start:2 end:4

returns #([10,10], [1,1], [2,2], [4,4], [5,5], [3,3])

So only the 2nd – 5th values were sorted…..

and we can also pass extra user-defiend arguments to our sorting function, for instance imagine we didn’t want to test distance from [0,0] we wanted to test from [10,10] instead….

fn myqSortFunction v1 v2 hittest: =
 (
 local d = distance hittest v1
 local dd = distance hittest v2
case of
 (
 (d < dd) : -1 (d > dd) : 1
 default: 0
 )
 )
vals = #([10,10],[5,5],[4,4],[2,2],[1,1],[3,3])
 qSort vals myqSortFunction hittest:[10,10]
 vals

So we’ve added an extra parameter to our qSort function and we’re passing an extra arguement to qSort but mapping it to our extra parameter otherwise qSort would grumble about an incorrect amount of arguments.

Advertisements

About davewortley

Somewhere between an artist and a programmer, I like technical things, but being creative. I love problem solving and coming up with elaborate solutions. This blog is where I shall share ideas, tips, tutorials and anything that amuses me.
This entry was posted in Lessons, MaxScript. Bookmark the permalink.

2 Responses to Lesson 12: qSort

  1. Thank you for sharing! I’d just like to say how much I appreciate the blog! Very informative tips and tricks!

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s