In Adding Functionality – 2a I laid out the UI changes to support sorting of the results of Dick Kusleika’s VBE Find.
In this post, I develop the actual sort routine.
To recap, the task is to sort a 2D matrix on any number of columns. The sort columns are listed in a 1D array, with each entry in this array identifying one sort column. So, the sort routine’s signature is
Sub doSort(DataArr(), SortCols() As Integer)
End Sub
The routine uses what is called the Bubble Sort. It is fast for “small” matrices, and will be more than adequate for our needs.
The Bubble Sort essentially goes through the matrix row by row. For each row, it compares that row with every other row between itself and the end of the matrix. If necessary, it swaps the two rows. Consequently, once we are done with a particular row, we never need to reexamine it again. And, that’s why it’s called a Bubble Sort. The results “bubble” to their correct spot.
Sub doSort(DataArr(), SortCols() As Integer)
If ArrLen(DataArr) = 0 Or ArrLen(SortCols) = 0 Then Exit Sub
‘Swap the rows of DataArr as needed to perform an ascending sort
Dim I As Long, J As Long
For I = LBound(DataArr) To UBound(DataArr) – 1
For J = I + 1 To UBound(DataArr)
if row_I_key > row_J_key then swapRow DataArr, I, J
Next J
Next I
End Sub
That’s it. At its core, that’s the Bubble Sort. If we had a single key to sort on, we’d use the test DataArr(I,key-column) > DataArr (J, key-column)
. However, in this case, we have to cater to possibly multiple keys in the SortCols array. So, we write a slightly more complex comparison routine — and in the process also convert a number provided as a string to a numeric value.
To process multiple keys, we start with the ‘outermost’ key. If we can decide on the relative positions of the 2 records, we don’t have to check the next key. However, if the 2 key values are equal, we check the next key.
Option Explicit
Option Base 0
Option Compare Text
Function ArrLen(Arr, Optional whatDim As Integer = 1)
ArrLen = UBound(Arr, whatDim) – LBound(Arr, whatDim) + 1
End Function
Sub swapRow(DataArr, R1 As Long, R2 As Long)
Dim J As Long
For J = LBound(DataArr, 2) To UBound(DataArr, 2)
Dim Temp
If TypeOf DataArr(R1, J) Is Object Then
Set Temp = DataArr(R1, J)
Set DataArr(R1, J) = DataArr(R2, J)
Set DataArr(R2, J) = Temp
Else
Temp = DataArr(R1, J): DataArr(R1, J) = DataArr(R2, J): DataArr(R2, J) = Temp
End If
Next J
End Sub
Sub doSort(DataArr(), SortCols() As Integer)
If ArrLen(DataArr) = 0 Or ArrLen(SortCols) = 0 Then Exit Sub
‘Swap the rows of DataArr as needed to perform an ascending sort
Dim I As Long, J As Long
For I = LBound(DataArr) To UBound(DataArr) – 1
For J = I + 1 To UBound(DataArr)
Dim SortColIdx As Integer
SortColIdx = LBound(SortCols)
Dim PairDone As Boolean: PairDone = False
Do
Dim X1, X2, SortCol As Long
SortCol = SortCols(SortColIdx)
X1 = DataArr(I, SortCol): X2 = DataArr(J, SortCol)
If IsNumeric(X1) And IsNumeric(X2) Then X1 = CDbl(X1): X2 = CDbl(X2)
If X1 > X2 Then
swapRow DataArr, I, J
PairDone = True
ElseIf X1 < X2 Then
PairDone = True
Else
SortColIdx = SortColIdx + 1
End If
Loop Until PairDone Or SortColIdx > UBound(SortCols)
Next J
Next I
End Sub
The algorithm I eventually implemented uses an ‘index array’ to track the final sequence of the rows in the data matrix. Use of an index array means that each swap involves just 1 element rather than every column in the data matrix.
Here’s where one would see a benefit. Suppose we have 3 records with the keys 33,22, and 11, respectively. Then, the final, and desired, sequence would be the records with keys 11,22, and 33.
With a Bubble Sort we would get the following swaps: (33,22,11) -> (22,33,11) -> (22,11,33) -> (11,22,33). So, we have to swap the rows 4 times, with each swap requiring an exchange of all the columns in the 2 rows, one at a time.
Alternatively, we could build an array with the record numbers in it, i.e., (1,2,3). Now, we change only the contents of this array leaving the original array alone. So, the four swaps would yield the index array (1,2,3) -> (2,1,3) -> (2,3,1) -> (3,2,1). This gives us the sequence of the final output, i.e., row 3, row 2, and finally row 1. So, we would have 4 swaps with the index array and 3 sequence moves for the data matrix.