26. November 2020

Fast Sorting Of Arrays

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 Questions?

Want to know more about this topic or have another question? Please contact us!

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…

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…

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…

more

INOSIM Support

During usual business hours

Germany +49 231 97 00 250

USA +1 214 663 3101

support@inosim.com