How do I sort an array?

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.

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:

# 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

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:

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

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