Preserving sort order with equal keys

[Richard Russell]

Suppose you have a key array key() and a data array dat() and you want to sort the data array in ascending order of key. That's straightforward using the sortlib library:

Code: Select all

      C% = DIM(key(),1) + 1
      CALL Sort%, key(0), dat(0)

But suppose, additionally, that two or more elements in the key array are identical, and in that case you want the order in the data array to be unaffected. This is more difficult, because the way the library works is that when there are identical elements in one array it uses the next array to determine the sort order. And if the elements in the next array are identical too, it uses the array after that, and so on.

So the above code won't leave the data elements unaffected if the keys are identical, it will sort them according to their values. How can we achieve the desired behaviour? The answer is to introduce an additional, dummy, array which determines the order when the keys are identical:

Code: Select all

      DIM dummy%(DIM(key().1))
      FOR I% = 0 TO DIM(dummy%(),1) : dummy%(I%) = I% : NEXT
      C% = DIM(key(),1) + 1
      CALL Sort%, key(0), dummy%(0), dat(0)

Now, if two or more elements in the key array are identical, the dummy array will control the sort order, and as that is already in ascending order the data elements won't be sorted!

Exercise: If we want to do a descending sort rather than an ascending sort, but still keep the order of the data elements the same when the keys are identical, what change do we need to make to this code?