Implement Advanced Sorting Algorithms With Excel VBA

1. QuickSort Algorithm in VBA

QuickSort is a divide-and-conquer algorithm that works by selecting a pivot element from the array, partitioning the other elements into two sub-arrays (elements less than the pivot and elements greater than the pivot), and then recursively sorting the sub-arrays.

Steps to Implement QuickSort in VBA:

1. Choose a pivot element (usually the last element).
2. Partition the array into two sub-arrays.
3. Recursively apply the same process to both sub-arrays.

Here’s how you can implement it in VBA:

Sub QuickSortExample()
    Dim arr As Variant
    arr = Array(3, 7, 8, 5, 2, 1, 4, 6) ' Sample array
    ' Call the QuickSort function
    QuickSort arr, LBound(arr), UBound(arr)
    ' Output the sorted array in the Immediate Window (Ctrl + G)
    For i = LBound(arr) To UBound(arr)
        Debug.Print arr(i)
    Next i
End Sub
' QuickSort Function
Sub QuickSort(ByRef arr As Variant, ByVal low As Long, ByVal high As Long)
    Dim pivot As Long
    Dim i As Long, j As Long
    Dim temp As Variant
    If low < high Then
        ' Choose a pivot and partition the array
        pivot = Partition(arr, low, high)
        ' Recursively sort the sub-arrays
        QuickSort arr, low, pivot - 1
        QuickSort arr, pivot + 1, high
    End If
End Sub
' Partition Function to rearrange elements around pivot
Function Partition(ByRef arr As Variant, ByVal low As Long, ByVal high As Long) As Long
    Dim pivot As Variant
    Dim i As Long, j As Long
    Dim temp As Variant
    pivot = arr(high) ' Last element is the pivot
    i = low - 1 ' Pointer for smaller element
    For j = low To high - 1
        If arr(j) <= pivot Then
            i = i + 1
            ' Swap arr(i) and arr(j)
            temp = arr(i)
            arr(i) = arr(j)
            arr(j) = temp
        End If
    Next j
    ' Swap arr(i + 1) and arr(high) (the pivot)
    temp = arr(i + 1)
    arr(i + 1) = arr(high)
    arr(high) = temp
    Partition = i + 1 ' Return the pivot index
End Function

Explanation of the QuickSort Code:

1. QuickSort Subroutine:
   • This subroutine takes the array arr and sorts it in-place.
   • It calls the Partition function to rearrange the array and then recursively sorts the sub-arrays.
   • low and high are the indices indicating the current sub-array being sorted.
2. Partition Function:
   • The pivot is selected as the last element of the sub-array (arr(high)).
   • It rearranges the elements so that all elements less than the pivot are on the left and all elements greater than the pivot are on the right.
   • It returns the pivot’s new index, which divides the array into two sub-arrays.

2. MergeSort Algorithm in VBA

MergeSort is also a divide-and-conquer algorithm that divides the array into two halves, recursively sorts them, and then merges the sorted halves.

Steps to Implement MergeSort in VBA:

1. Divide the array into two halves.
2. Recursively sort the two halves.
3. Merge the two sorted halves.

Here’s how you can implement it in VBA:

Sub MergeSortExample()
    Dim arr As Variant
    arr = Array(3, 7, 8, 5, 2, 1, 4, 6) ' Sample array
    ' Call the MergeSort function
    MergeSort arr, LBound(arr), UBound(arr)
    ' Output the sorted array in the Immediate Window (Ctrl + G)
    For i = LBound(arr) To UBound(arr)
        Debug.Print arr(i)
    Next i
End Sub
' MergeSort Function
Sub MergeSort(ByRef arr As Variant, ByVal low As Long, ByVal high As Long)
    Dim mid As Long
    If low < high Then
        mid = (low + high) \ 2 ' Find the middle of the array
        ' Recursively sort the left and right halves
        MergeSort arr, low, mid
        MergeSort arr, mid + 1, high
        ' Merge the sorted halves
        Merge arr, low, mid, high
    End If
End Sub
' Merge Function to merge two halves
Sub Merge(ByRef arr As Variant, ByVal low As Long, ByVal mid As Long, ByVal high As Long)
    Dim tempArr() As Variant
    Dim i As Long, j As Long, k As Long
    Dim leftSize As Long, rightSize As Long
    leftSize = mid - low + 1
    rightSize = high - mid
    ' Create temporary arrays for the two halves
    ReDim leftArr(leftSize - 1)
    ReDim rightArr(rightSize - 1)
    ' Copy data into temporary arrays
    For i = 0 To leftSize - 1
        leftArr(i) = arr(low + i)
    Next i
    For j = 0 To rightSize - 1
        rightArr(j) = arr(mid + 1 + j)
    Next j
    i = 0
    j = 0
    k = low
    ' Merge the temporary arrays back into the original array
    While i < leftSize And j < rightSize
        If leftArr(i) <= rightArr(j) Then
            arr(k) = leftArr(i)
            i = i + 1
        Else
            arr(k) = rightArr(j)
            j = j + 1
        End If
        k = k + 1
    Wend
    ' Copy any remaining elements from leftArr or rightArr
    While i < leftSize
        arr(k) = leftArr(i)
        i = i + 1
        k = k + 1
    Wend
    While j < rightSize
        arr(k) = rightArr(j)
        j = j + 1
        k = k + 1
    Wend
End Sub

Explanation of the MergeSort Code:

1. MergeSort Subroutine:
   • This subroutine recursively divides the array into two halves until each sub-array contains only one element.
   • It calls the Merge function to combine the two halves into a sorted array.
2. Merge Function:
   • The Merge function combines two sorted sub-arrays into a single sorted array.
   • It uses temporary arrays (leftArr and rightArr) to hold the elements of the two halves.
   • It compares the elements from both halves and merges them in sorted order into the original array.

How to Use These Sorting Algorithms:

• You can call the QuickSortExample or MergeSortExample procedure in the VBA editor to test these sorting algorithms.
• You can replace the sample array arr with any data range in Excel, for example:
• arr = Range(« A1:A10 »).Value ‘ Get values from cells A1 to A10

Ensure the range contains numerical data for sorting purposes.

Conclusion:

Both QuickSort and MergeSort are efficient sorting algorithms that work well with large datasets. QuickSort is typically faster due to its partitioning strategy, but MergeSort is more predictable in terms of performance since it guarantees O(n log n) time complexity in the worst case. You can implement either algorithm in Excel VBA depending on your needs and the size of the data you’re working with.