Quick Jump
Introduction | Example | Tutorial | Applications | Comments

Introduction - VBA Quicksort

The VBA quicksort macro is a fast way to sort VBA arrays. The VBA Quicksort macro in this tutorial is much more efficient than the VBA bubble sort macro I showed last week, so it can be used to quickly sort both small and large one dimensional VBA arrays .

Near the bottom of this tutorial, I’ll show you the results of my benchmark comparing the quicksort and bubble sort macros in Excel VBA. The results are incredible!


Example - VBA Quicksort

Super Fast Quicksort Macro

Sub Quicksort(vArray As Variant, arrLbound As Long, arrUbound As Long)
'Sorts a one-dimensional VBA array from smallest to largest
'using a very fast quicksort algorithm variant.
Dim pivotVal As Variant
Dim vSwap    As Variant
Dim tmpLow   As Long
Dim tmpHi    As Long
 
tmpLow = arrLbound
tmpHi = arrUbound
pivotVal = vArray((arrLbound + arrUbound) \ 2)
 
While (tmpLow <= tmpHi) 'divide
   While (vArray(tmpLow) < pivotVal And tmpLow < arrUbound)
      tmpLow = tmpLow + 1
   Wend
  
   While (pivotVal < vArray(tmpHi) And tmpHi > arrLbound)
      tmpHi = tmpHi - 1
   Wend
 
   If (tmpLow <= tmpHi) Then
      vSwap = vArray(tmpLow)
      vArray(tmpLow) = vArray(tmpHi)
      vArray(tmpHi) = vSwap
      tmpLow = tmpLow + 1
      tmpHi = tmpHi - 1
   End If
Wend
 
  If (arrLbound < tmpHi) Then Quicksort vArray, arrLbound, tmpHi 'conquer
  If (tmpLow < arrUbound) Then Quicksort vArray, tmpLow, arrUbound 'conquer
End Sub

Write better macros in half the time
I want to help you write macros with my Excel VBA tutorials and VBA code examples. That’s why I developed this unique 3-part VBA training program to help you quickly learn VBA and gain access to my entire macro library without ever leaving Excel.


Tutorial - VBA Quicksort

About Quicksort

The quicksort algorithm is what’s known as a “divide and conquer” algorithm. First, it identifies a pivot value, which is nothing more than a random element inside your array. The example macro assumes the very center element, but it could be any element. After that, it partitions the array by moving elements that are larger than your pivot value to one side of your array and moving elements that are smaller than your pivot to the other side. This is the divide part of “divide and conquer.”

After dividing and partitioning around the pivot, the quicksort algorithm conquers by recursively calling itself to process the two halves, or subarrays, of the original array.

Although the worst case performance of the quicksort algorithm is proportional to N^2 (where N is the number of elements in the array), just like bubble sort, it hardly ever takes this long. As a matter of fact, the average performance is classified as a complexity on the order of N*log(N) instead of N^2. That’s much faster than bubble sort! I’ll prove it in a little while.

Like I said earlier, the example macro pivots around the middle element. This is technically a little slower than pivoting around the far left or far right element, but it reduces the likelihood of the algorithm degrading to an N^2 number of iterations if you accidentally try to sort an array that’s already nearly sorted.

Why use the VBA Quicksort algorithm

Because the VBA quicksort algorithm is typically ridiculously faster than the bubble sort algorithm! What other reasons do you need? True, it’s a little harder to understand and the recursive nature makes it more challenging to program, but finding yourself a good quicksort algorithm, like the one in this tutorial, can save you and your code a tremendous amount of time.

To demonstrate what I mean, let’s compare the quicksort and bubble sort algorithms using VBA.

VBA Quicksort vs VBA Bubble Sort

I created a one dimensional VBA array with 25,000 elements populated with random numbers between 0 and 10,000. First, I sorted the array using the VBA bubble sort algorithm from last week’s tutorial. On my machine, bubble sort took a whopping 22.64 seconds.

I then took the exact same array and sorted it using the VBA quicksort algorithm presented in this tutorial. The differences were astonishing. The quicksort method only took 0.07 seconds.

The VBA quicksort macro was 323x faster than the VBA bubble sort macro!

It’s worth noting that the smaller your array size gets, the closer the average performance of the two macros becomes. Even so, it’s clear running the quicksort macro is much faster than using a sluggish bubble sort algorithm.

Here’s my benchmark comparing the performance (in seconds) of the VBA quicksort and VBA bubble sort macros as a function of array size using identical arrays for each comparison:


VBA Quicksort vs Bubble Sort Benchmark

N  Quicksort   Bubble Sort  
25,000 0.070 22.643
10,000 0.027 3.551
5,000 0.016 0.891
1,000 0.004 0.059

Time (in seconds) to sort VBA arrays of size N


These results illustrate why I recommend only using bubble sort for small arrays.

The quicksort algorithm is complex so chances are you won’t want to program it from scratch. To implement the quicksort sorting algorithm into your Excel projects in a jiffy, add the quicksort macro to your favorites in wellsrPRO and select it from your Excel ribbon whenever you need it.

How to Use the VBA Quicksort Macro

Let’s say you have a column of data in Column A of your spreadsheet. You store each element in a one-dimensional VBA array and you want to sort the array from smallest to largest. You may find yourself needing to sort your data like this if you want to perform some statistical analysis, for example, on the bottom 10% or the middle 20% of data. Here’s how you would call the Quicksort example macro:

Sub ProcessData_Quicksort()
'Example macro to show you how to add a column of data to an array
'and sort the data from smallest to largest using VBA Quicksort.
Dim MyData() As Variant
Dim i As Long, LastRow As Long

'Store column of data into array
LastRow = Range("A" & Rows.Count).End(xlUp).Row
ReDim MyData(1 To LastRow)
For i = 1 To LastRow
    MyData(i) = Range("A" & i)
Next i

'Now sort your array using the VBA Quicksort macro
Call Quicksort(MyData(), LBound(MyData), UBound(MyData))
'
'From here on, your "MyData" array is sorted from smallest to largest
'
End Sub

Notice the Call Quicksort line has three arguments. The first argument is your one-dimensional array, MyData. The second and third arguments are the lower bound and upper bound of your array. The “lower bound and upper bound” is another way of saying “first element and last element” of your array. These arguments are necessary since quicksort is a recursive algorithm. I can’t just hardwire the boundaries because the quicksort algorithm needs to divide and conquire by identifying its own pivot points and partitions. In my example, I used the LBound and Ubound functions to define the boundaries the first time. The VBA script does the rest as part if its recursive logic.

Anyway, once you call quicksort, your VBA array will be sorted from smallest to largest and you’ll be able to do whatever you want with your sorted VBA array.


Application Ideas

Although I find myself defaulting to the bubble sort algorithm in most of my spreadsheets, this tutorial has convinced me I need to switch to a VBA quicksort macro. The benchmark proves quicksort is so much faster than bubble sort (on average), which is very important when you’re working with a slower programming language like VBA.

You definitely want to use VBA quicksort instead of bubble sort when working with large arrays. How do you plan on using this sorting macro? Let me know in the comments section!


Closing Thoughts

Before commenting, please take a moment to share this article with your friends on Facebook, Twitter, and Google+. Social media is a great way to grow the site and reach more users, so I genuinely appreciate it when you share my articles with friends on your favorite platform! :)


About Ryan Wells

Ryan Wells

Ryan Wells is a Nuclear Engineer and professional VBA Developer. He is the lead developer of several VBA products, including Mouse To Macro. See more Excel products, including online courses and books, by visiting the Excel VBA Store.