How do I sort an array?

This lesson describes a method to sort arrays and how to use it in your code, moving from a specific case to a more general form.  Sample code is provided.

Introduction

Introduction

A common task performed by computer applications is to take an array of items and sort them into a more useful or presentable order, for instance ordering the entries in an address book alphabetically so the user will be able to find a particular entry more quickly.  A sorted array also has the advantage that searches can be performed very quickly using a boolean search which can eliminate half the possible matches at each step.

 

Sorting arrays by sorting keys

LiveCode arrays are more than simple numerically indexed lists of values.  The entries in an array can be also be stored and referenced using key values containing text strings, and the mapping of each key to each entry can convey more meaning than just the order of the elements, which simply reordering the entries in the array would disrupt.

One method of ordering the entries in another is to first sort the keys of the array using the values for each key.  In LiveCode this can be done as follows:

Key sorting code

   # first we set up the entries in our array
   local tArray
   put "Miller, Kevin" into tArray[1]
   put "Beaumont, Benjamin" into tArray[2]
   put "Kenyon, Oliver" into tArray[3]
   put "Macphail, Ian" into tArray[4]
   put "Pepe, Tio" into tArray[5]
   
   # now we fetch the keys and sort them using the array entry values
   get the keys of tArray
   sort lines of it by tArray[each]
   split it by return

How this works

The "sort lines of [list] by [expression]" form of the sort command allows us to specify an expression to produce a value which acts as a stand-in for each line being sorted.  In the above example, rather than directly compare the values of each key, we are comparing the values of the array entry for that key.

The sorted keys are then split to create a new array which maps each position in an ordered array to the entry in the original array at that position.

In our example this produces the following mapping:

Mapping from ordered position to key and value

Mapping from ordered position to key and value

Creating our new sorted array

Now that we have a mapping array we can use it to create a new array with the entries of the original array in a sorted order.  To do so we loop over the elements of the map to fetch each entry in turn and place it into the appropriate position in our new array:

   local tSortedArray
   local tNextIndex
   
   put 1 into tNextIndex
   repeat for each element tIndex in it
      put tArray[tIndex] into tSortedArray[tNextIndex]
      add 1 to tNextIndex
   end repeat

 

Writing an array sort function

Now that we have a way to create a sorted array from an unordered array we can write a LiveCode function to do this for us:

function sortedArray @pArray
   local tSortedArray
   local tNextIndex
   
   # fetch the keys and sort them using the array entry values
   get the keys of pArray
   sort lines of it by pArray[each]
   
   split it by return
   
   # create a new sorted array using the mapped keys
   put 1 into tNextIndex
   repeat for each element tIndex in it
      put pArray[tIndex] into tSortedArray[tNextIndex]
      add 1 to tNextIndex
   end repeat
   
   return tSortedArray
end sortedArray

So anywhere that we need to sort an array we can do the following:

put sortedArray(tArray) into tSortedArray

 

 

0 Comments

Add your comment

E-Mail me when someone replies to this comment