Sorting and stability

Often you want to sort into alphabetical order or numerical order. And there are various ways to accomplish this.

But what if you need to sort first numerically and then alphabetically and maybe several other additional criteria ? How does this affect the overall result ?

It might be nice to make it so that the second sort doesn’t break the ordering the first sort did. And there are sorting schemes that do this.

For instance if you had the following data :

35,33, 42,10,14,19,26,44,26,31

and used a “stable sorting algorithm” then you should see the following (note that items have been numbered so its possible to keep track of which item is where in the newly sorted data)

Note that 26 appears twice in the input and, in the output the two instances of 26 retain their relative order. The 26 at item 6 appears in the output before the 26 in item 8.

Wikipedia defines a “stable sort” as

Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

https://en.wikipedia.org/wiki/Category:Stable_sorts

Fortunately Xojo uses a RADIX sort which IS a stable sort so subsequent sorting wont ruin the relative order of elements. This code shows this occurring.

Dim rawData() As Integer = Array(35,33, 42,10,14,19,26,44,26,31)

Dim indexes() As Integer
Dim data() As Integer

For i As Integer = 0 To rawData.Ubound
  indexes.append 0i
  data.append rawData(i)
Next


data.sortwith indexes

Break

Whats harder to see is that if you then sort the data in another way that the relative orders are preserved in the result.

The following more complex code shows this. We first sort by ascending numeric value, and then by ascending alphabetical value.

Dim rawData() As Integer = Array(35,33, 42,10,14,19,26,44,26,31)
Dim alphaRawData() As String = Array("f", "z", "c", "d", "e", "a", "b", "q", "s", "b")

Dim indexes() As Integer
Dim data() As Integer

For i As Integer = 0 To rawData.Ubound
  indexes.append i
  data.append rawData(i)
Next

data.sortwith indexes, alphaRawData

Break

alphaRawData.SortWith data, indexes

Break

Again note that the 26’s retain their relative order. Sorting multiple times doesnt ruin the relative order of the input items.

Even if we chnage the data so that the two 26’s use the same alphabetic value they will retain their relative order.