Lowell Boggs, Jr. - 2016-05-21

How to implement a sort function

Starting in brash 1.2.0, there is support for array variables which act much like the GNU Bash arrays.

There are two types of arrays: normal "vector" style arrays, and associative arrays which act like STL maps.

In Bash, the associative arrays are not (to my knowledge) implemented as sorted maps. I think they are hash tables. But brash implements them as map<string,string>. This has the advantage of providing the ability to write a sort routine.

The basic idea is to store the data that is to be sorted as keys in an associative array. There is a problem, however: keys cannot be duplicated!

On the other hand, the values associated with a given key value can be used as a count of matches of that particular key value. Each time you go to insert something into the associative array, you increment the count associated with the value. Once the associative array is populated, you use the following algorithm to print the input data in sorted form:

for each key value in the associative array
   get the count of references to that key value
   for each reference, print the key value again

Obviously this is not the world's best sorting strategy and there are many flaws that can arise but it works pretty well most of the time on most text files.

Note that the comparison algorithm is a binary comparison of the strings in the keys, so you won't get a proper lexicographical sort -- but you will get a plain old binary sort.