10
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
7
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ You mean to init r = right - 1? But that breaks if the pivot is the single greatest value. \$\endgroup\$ – cheezsteak Apr 18 '14 at 18:32
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.