   • 26. November 2020

# Fast Sorting Of Arrays

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 Bubblesort 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.

## 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 As Variant, 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 As Variant
Dim vSwap As Variant
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
Wend
While (P < vArray(j) And j > firstRow)
j = j - 1
Wend
If (i <= j) Then
vSwap = vArray(i)
vArray(i) = vArray(j)
vArray(j) = vSwap
i = i + 1
j = j - 1
End If
Wend

' recursion
If (firstRow < j) Then Quicksort (vArray, firstRow, j)
If (i < lastRow) Then Quicksort (vArray, i, lastRow)
End If
End Sub``````

## Sorting a 2-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 As Variant, _
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 As Variant
Dim P As Variant

If firstRow = -1 Then firstRow = LBound(vArray)
If lastRow = -1 Then lastRow = UBound(vArray)

firstCol = LBound(vArray, 2)
lastCol = UBound(vArray, 2)
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
Wend
While (vArray(j, lColumn) > P) And j > firstRow
j-=1
Wend
Else
' sort order descending
While (vArray(i, lColumn) > P) And i < lastRow
i+=1
Wend
While (vArray(j, lColumn) < P) And j > firstRow
j-=1
Wend
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 Sub``````

## More Tips & Tricks

19. July 2021

#### Custom Gantt Colors

The INOSIM Gantt chart provides the option to color allocation bars on basis of various predefined attributes. In the order view, it is possible to…

21. June 2021

#### Printing Complex Gantt Charts As PDFs

Printing Complex Gantt Charts As PDFs In this tip, you learn how to create PDFs which display a selected time range of a complex Gantt…

23. February 2021

#### INOSIM Remote Control via the COM-Interface

Did you know INOSIM can be remote-controlled by any program that can send signals via the COM-Interface? Let us sketch a scenario of how this…

INOSIM Support