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 that 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 by using a boolean search which can eliminate half of the possible matches at each step.

 

Sorting arrays by sorting keys

revTalk 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 revTalk 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 revTalk 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