PillarSoft

Contributed by: Scott Tietjen

Every now and then, you might need to sort the contents of a simple stemmed variable array. The following snippet implements what is called a "bubble" or "elevator" sort, which according the the algorithm books is probably the slowest sort possible, taking on the order of n-squared time to sort n items in a list, while using minimal additional memory (just a few fields to allow swapping of entries). However, if you don't have an outrageously large list to deal with, this is probably good enough for most efforts. I would start to worry about how long it takes with item counts in the hundreds or thousands -- your mileage may vary, depending on memory and processor speed. For example, when I ran this code on a large MVS mainframe, I decided to not use it when I needed to sort more than 1000 entries, but for sorting 500-999 entries, although it took a while, did not take "too long" (for me).

Notes:

1. Standard format array -- sucessive items in .1 thru .n, with n stored in .0
2. The list is sorted ascending -- for decending reverse the greater than sign to a less than sign in the If statement on the 6th line.
3. The array is sorted "in place" -- when finished, item .1 will have the smallest value, and so on until .n has the largest value.
4. If you need to sort several parallel stemmed variables based on the value of one of them, just add the additional swaps of the extra variables to the body of the Then clause, repeating the format of lines 8-10.
5. If you have a lot of parallel stemmed variables that you want to sort relative to one of them, but you don't want to waste time moving them around memory, please see the second snippet. By creating special Key and Index arrays, and sorting them, you can then virtually sort the arrays; a variation could be used to deal with a multi-dimensional array.

/* Simple sort algorithm for stemmed variable Stemvar. */

Swapped = 1
Do While Swapped
  Swapped = 0
  Do I = 1 to (Stemvar.0 - 1)
    J = I + 1
    If Stemvar.I > Stemvar.J  /* sorts ascending */
      Then Do
        Hold      = Stemvar.I
        Stemvar.I = Stemvar.J
        Stemvar.J = Hold
        Swapped   = 1
        End
    End I
  End

/* Sorting several parallel stemmed vars StemA., StemB., StemC. etc. using a index */

Do I = 1 to StemA.0
  SortKey.I = StemA.I        /* copy the sort key to its own array */
  SortIdx.I = I              /* and create an index for it         */
  End I
SortKey.0 = StemA.0
SortIdx.0 = StemA.0

Swapped = 1
Do While Swapped
  Swapped = 0
  Do I = 1 to (SortKey.0 - 1)
    J = I + 1
    If SortKey.I > SortKey.J  /* sorts ascending */
      Then Do
        Hold      = SortKey.I
        SortKey.I = SortKey.J
        SortKey.J = Hold
        Hold      = SortIdx.I
        SortIdx.I = SortIdx.J
        SortIdx.J = Hold
        Swapped   = 1
        End
    End I
  End

Do I = 1 to SortIdx.0  /* Display the new virtually sorted arrays */
  J = SortIdx.I
  Say StemA.J StemB.J StemC.J
  End I