Fast Sorting Of Arrays And Tables
When sorting arrays, the runtime of the applied sorting procedure may play a crucial role. For smaller amounts of data, that may not yet be very important, so that easy-to-implement procedures such as Bubble sort are still acceptable. However, in the case of large amounts of data, they are self-prohibiting. In the following, Quicksort is introduced, a method belonging to the fastest sorting methods which is also suitable for large amounts of data. In this tip and trick, this algorithm was implemented for arrays and tables in WWB.NET and a sample model with test data is provided.
Divide and Conquer
The sorting algorithm works according to the Divide and Conquer principle: First, one item, preferably in the middle of the entire area, is selected (the so-called Pivot element) and thus the area is divided into two parts. All items that are smaller than the selected Pivot element are placed in the first area, all elements that are larger are placed in the second area. Items of equal size remain where they are.
Subsequently, each of the sub-areas is again treated according to the same procedure. This means that subareas are created in each subarea, in which the items again are divided according to their size. This procedure is continued until only parts of length 1 are left (recursion)
In addition to the high speed, a further advantage of this process is that no additional storage space is required, since the individual items are only exchanged within the array.
Sorting a list
The first code example shown here can be used to sort a simple list (one-dimensional array). To do this, the array and the indexes of the first and last line of the array to be sorted are passed to the routine. By specifying these indices, it is possible to sort only a certain range of a list. After executing the routine, the items are listed in ascending order.
Public Sub Quicksort (vArray, firstRow As Long, lastRow As Long)
'------------------------------------------------------------------------
' Sorts a one-dimensional VBA array from smallest to largest
' Input: vArray array 1dim array, containing the data to be sorted
' firstRow long first line of the area to be sorted
' lastRow long last line of the area to be sorted
'------------------------------------------------------------------------
Dim i As Long
Dim j As Long
Dim P
Dim vSwap
If lastRow >= 0 Then
i = firstRow
j = lastRow
P = vArray((firstRow + lastRow) \ 2) ' Pivot element
While (i <= j)
While (vArray(i) < P And i < lastRow)
i = i + 1
End While
While (P < vArray(j) And j > firstRow)
j = j - 1
End While
If (i <= j) Then
vSwap = vArray(i)
vArray(i) = vArray(j)
vArray(j) = vSwap
i = i + 1
j = j - 1
End If
End While
' recursion
If (firstRow < j) Then Quicksort (vArray, firstRow, j)
If (i < lastRow) Then Quicksort (vArray, i, lastRow)
End If
End SubFor example, the list List (as a One-Dimensional Array) can be sorted completely:
Call Quicksort(List, LBound(List), UBound(List))Sorting a two-dimensional array
The second code example shown here works according to the same procedure, but here two-dimensional arrays are sorted. In addition to the array to be sorted, the following parameters are also passed to the routine:
- Parameter lColumn: Specifies which column is to be sorted.
- Parameter lSortOrder: Order of sorting (ascending or descending).
- Parameter firstRow: Index of the first line of the array to be sorted (see above).
- Parameter lastRow: Index of the last line of the array to be sorted (see above).
Public Sub Quicksort2Dim (vArray , _
Optional ByVal lColumn As Long = 0, _
Optional lSortOrder As Long = 1, _
Optional ByVal firstRow As Long = -1, _
Optional ByVal lastRow As Long = -1)
'------------------------------------------------------------------------
' Sorts a 2-dimensional array according to the specified sort order
' Input: vArray array 2dim array, containing the data to be sorted
' lColumn long column, which is to be sorted (optional)
' lSortOrder long Sort order, 0 = descending, 1 = ascending) (optional)
' firstRow long first line of the area to be sorted (optional)
' lastRow long last line of the area to be sorted (optional)
'------------------------------------------------------------------------
Dim i As Long
Dim j As Long
Dim u As Long
Dim firstCol As Integer
Dim lastCol As Integer
Dim h
Dim P
If firstRow = -1 Then firstRow = LBound(vArray)
If lastRow = -1 Then lastRow = UBound(vArray) 'vArray.RowCount '
firstCol = LBound(vArray, 2) '1 '
lastCol = UBound(vArray, 2) 'vArray.ColumnCount '
i = firstRow
j = lastRow
P = vArray((firstRow + lastRow) / 2, lColumn)
Do
If lSortOrder = 1 Then
' sort order ascending
While (vArray(i, lColumn) < P) And i < lastRow
i+=1
End While
While (vArray(j, lColumn) > P) And j > firstRow
j-=1
End While
Else
' sort order descending
While (vArray(i, lColumn) > P) And i < lastRow
i+=1
End While
While (vArray(j, lColumn) < P) And j > firstRow
j-=1
End While
End If
If (i <= j) Then
For u = firstCol To lastCol
h = vArray(i, u)
vArray(i, u) = vArray(j, u)
vArray(j, u) = h
Next u
i += 1
j -= 1
End If
Loop Until (i > j)
' recursion
If (firstRow < j) Then Quicksort2Dim (vArray, lColumn, lSortOrder, firstRow, j)
If (i < lastRow) Then Quicksort2Dim (vArray, lColumn, lSortOrder, i, lastRow)
End SubSo, for example, if you want to sort TwoDim after the second column in ascending order, the following call can be executed:
Call Quicksort2Dim(TwoDim, 1, 1, -1, -1)Here, the parameter is lColumn=1 since the column index of the array starts at 0.
Sorting a table
The third code example shown here also works according to the same procedure, but in this case table entries are sorted. In addition to the table to be sorted, the routine is provided with the same parameters as in the previous example.
Public Sub QuicksortTable (vTable As Table, _
Optional ByVal lColumn As Long = 1, _
Optional lSortOrder As Long = 1, _
Optional ByVal firstRow As Long = 1, _
Optional ByVal lastRow As Long = -1)
'------------------------------------------------------------------------
' Sorts a table according to the specified sort order
' vTable table, containing the data to be sorted
' lColumn long column, which is to be sorted (optional)
' lSortOrder long Sort order, 0 = descending, 1 = ascending (optional)
' firstRow long first line of the area to be sorted (optional)
' lastRow long last line of the area to be sorted (optional)
'------------------------------------------------------------------------
Dim i, k As Long
Dim j As Long
Dim u As Long
Dim firstCol As Integer
Dim lastCol As Integer
Dim h_i , h_j
Dim P
If lastRow = -1 Then lastRow = vTable.RowCount
If vTable.ColumnIndex = True Then
firstCol = 0
Else
firstCol = 1
End If
lastCol = vTable.ColumnCount
i = firstRow
j = lastRow
k = Int((firstRow + lastRow) / 2)
P = vTable( k, lColumn)
Do
If lSortOrder = 1 Then
' sort order ascending
While (vTable(i, lColumn) < P) And i < lastRow
i += 1
End While
While (vTable(j, lColumn) > P) And j > firstRow
j -= 1
End While
Else
' sort order descending
While (vTable(i, lColumn) > P) And i < lastRow
i+=1
End While
While (vTable(j, lColumn) < P) And j > firstRow
j-=1
End While
End If
If (i <= j) Then
For u = firstCol To lastCol
h_i = vTable(i, u) 'save value i
h_j = vTable(j, u) 'save value j
vTable(j, u) = Nothing 'overwrite value j with nothing (necessary for index)
vTable(i, u) = h_j 'overwrite i with j
vTable(j, u) = h_i 'write i into j
Next u
i += 1
j -= 1
End If
Loop Until (i > j)
' recursion
If (firstRow < j) Then QuicksortTable (vTable, lColumn, lSortOrder, firstRow, j)
If (i < lastRow) Then QuicksortTable (vTable, lColumn, lSortOrder, i, lastRow)
End SubFor example, the table object Tab can be sorted by the entries in the first column in descending order by:
QuicksortTable(Tab, 1, 0, 1, -1)Sorting a table alphabetically
Although text can be sorted with the subroutine QuicksortTable, it distinguishes between uppercase and lowercase (e.g., ZZ before aa). With the fourth code example shown here, table entries can be sorted alphabetically, independent of uppercase and lowercase. In addition to the table to be sorted, the routine is given the same parameters as in the previous two examples, whereby the entries in the column to be sorted (parameter: lColumn) are entered as a string.
Public Sub QuicksortAlpha (vTable As Table, _
Optional ByVal lColumn As Long = 1, _
Optional lSortOrder As Long = 1, _
Optional ByVal firstRow As Long = 1, _
Optional ByVal lastRow As Long = -1)
'------------------------------------------------------------------------
' Sorts a 2-dimensional array according to the specified sort order
' Input: vTable table, containing the data to be sorted
' lColumn long column, which is to be sorted (optional)
' lSortOrder long Sort order, 0 = descending, 1 = ascending) (optional)
' firstRow long first line of the area to be sorted (optional)
' lastRow long last line of the area to be sorted (optional)
'------------------------------------------------------------------------
Dim i, k As Long
Dim j As Long
Dim u As Long
Dim firstCol As Integer
Dim lastCol As Integer
Dim h_i , h_j
Dim P
If lastRow = -1 Then lastRow = vTable.RowCount
If vTable.ColumnIndex = True Then
firstCol = 0
Else
firstCol = 1
End If
lastCol = vTable.ColumnCount
i = firstRow
j = lastRow
k = Int((firstRow + lastRow) / 2)
P = vTable( k, lColumn)
Do
If lSortOrder = 1 Then
' sort order ascending
While (StrComp(vTable(i, lColumn), P, VbCompareMethod.vbTextCompare) < 0) And i < lastRow
i+=1
End While
While (StrComp(vTable(j, lColumn), P, VbCompareMethod.vbTextCompare) > 0) And j > firstRow
j-=1
End While
Else
' sort order descending
While (StrComp(vTable(i, lColumn), P, VbCompareMethod.vbTextCompare) > 0) And i < lastRow
i+=1
End While
While (StrComp(vTable(j, lColumn), P, VbCompareMethod.vbTextCompare) < 0) And j > firstRow
j-=1
End While
End If
If (i <= j) Then
For u = firstCol To lastCol
h_i = vTable(i, u) 'save value i
h_j = vTable(j, u) 'save value j
vTable(j, u) = Nothing 'overwrite value j with nothing (necessary for index)
vTable(i, u) = h_j 'overwrite i with j
vTable(j, u) = h_i 'write i into j
Next u
i += 1
j -= 1
End If
Loop Until (i > j)
' recursion
If (firstRow < j) Then QuicksortAlpha (vTable, lColumn, lSortOrder, firstRow, j)
If (i < lastRow) Then QuicksortAlpha (vTable, lColumn, lSortOrder, i, lastRow)
End SubFor example, if you want to sort the table object Tab alphabetically by the text fields in column 5 in ascending order, the following call can be executed:
QuicksortAlpha(Tab, 5, 1, 1, -1)Download
A sample model with all four subroutines including the necessary functions for reading and writing tables is available in the Download area (see button below).
More Questions?
Want to know more about this topic or have another question? Please contact us!
More Tips & Tricks
Animated Graphical Objects In INOSIM
Graphical auxiliary functions give live to your plant layout: By animation, you dynamically display filling level changes, transport movements of objects, or the status of…
When modeling a production process, it may happen that a certain property is not built into the software: the material of the equipment, or the…
Applying Table Objects
In INOSIM models, it can be very handy to organize the input for your recipes in Excel Tables, either to have a better overview over…
General Inquiries 
