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
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
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
Call Quicksort line has three arguments. The first argument is your one-dimensional array,
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.
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!
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! :)