In place quicksort

Question

I implemented my own sorting in VBA because it doesn't provide its own, and it's healthy to test yourself. It was surprisingly difficult and I ended up make a few tweaks that I didn't expect to make in order for it to sort.

Public Sub quicksort(ByRef arr As Variant, _
                     ByVal left As Integer, _
                     ByVal right As Integer)
    If right <= left Then Exit Sub  ' length == 1 already sorted
     'swap pivot it to end.  I'm not yet concerned about pivot selection
    Call swap(arr(CInt((left + right) \ 2)), arr(right)) 
    Dim r As Integer: r = right ' include the pivot in case it's the greatest value
    Dim l As Integer: l = left
    Dim p As Variant: p = arr(right) ' again pivot is at the end
    While l < r
        While arr(l) < p And l < r
            l = l + 1
        Wend
        While arr(r) >= p And l < r ' Right claims values which equal pivot
            r = r - 1
        Wend
        If l <> r Then Call swap(arr(l), arr(r))
    Wend
    ' Don't swap the same thing
    If l <> right Then Call swap(arr(right), arr(l))
    Call quicksort(arr, left, l - 1) 
    Call quicksort(arr, l + 1, right)
End Sub

Answer 1

VB6/VBA is a "bulky" language to read - If...End If, Sub...End Sub, While...Wend; compared to curly braces languages (Java, C#, etc.), VB6/VBA code, by the nature of its code block delimiters, makes pretty crowded code, even when written cleanly.

Give it some breathing vertical space:

Public Sub QuickSort(arr As Variant, ByVal left As Integer, ByVal right As Integer)

    'if length is 1, there's nothing to sort:
    If right <= left Or Not IsArray(arr) Then Exit Sub

    'swap pivot it to end. I'm not yet concerned about pivot selection
    Swap arr((left + right) \ 2), arr(right)

    ' include the pivot in case it's the greatest value:
    Dim r As Integer
    r = right 

    Dim l As Integer
    l = left

    ' pivot is at the end:
    Dim p As Variant
    p = arr(right) 

    While l < r

        While arr(l) < p And l < r
            l = l + 1
        Wend

        ' right claims values equal to pivot:
        While arr(r) >= p And l < r 
            r = r - 1
        Wend

        If l <> r Then Swap arr(l), arr(r)

    Wend

    ' only swap if values aren't equal:
    If l <> right Then Swap arr(right), arr(l)

    QuickSort arr, left, l - 1
    QuickSort arr, l + 1, right

End Sub

Couple points:

• Unless you have a massive parameters list, keep signatures on a single line.
• Method names should be PascalCase.
• : instruction separator is great for the immediate pane, but should be avoided in actual code - keep it single instruction per line as much as possible.
• Place comments just above the code you're commenting, this makes reading more vertically flowing.
• I don't think CInt cast/conversion is needed here, you're using the \ integer division operator, on two Integer variables - the result has to be an Integer, hence the conversion would be redundant.
• Call is a relic from ancient, stone-tablet-BASIC versions; dropping it allows you to also drop the parentheses that surround the parameters (not dropping the parentheses wouldn't compile).
• @user58697 is correct, the outer While loop could be extracted into its own method.
• What happens if arr isn't an array? I know, dumb edge case, but your method takes a Variant (it has to), and that could be literally anything. Guarding against that dumb error is fairly easy: IsArray(arr) must return True.

• I would avoid chopped-off and single-letter names, especially when they involve a lowercase l:

  • arr => items or values
  • p => pivotValue
  • r => rightIndex
  • l => leftIndex

Answer 2

Few notes.

• All algorithms on ranges are much simpler if the range is considered semi-open (that is, right is just beyond the last interesting element.
• The While l < r loop does a very important job; important enough to factor it into a separate function, Public Sub Partition
• One more thing you want to do is to eliminate a last tail-recursive call to quicksort. It is very well possible that the compiler will do it for you; still it is better to be explicit.

Answer 3

Just one comment: use Longs instead of Integers, sometimes it causes a dramatic improvement in speed (Excel converts Integers to Longs in the background).