Comparing and Swapping

Sorting is a simple operation. You compare the elements and swap the ones that are out of order until all are in order. A QuickSort does this differently than a Heap sort or an Insertion sort does, but all that matters to the programmer using the procedure is how you compare and swap. Both these operations can vary greatly, depending on what you’re sorting and how you want to sort it.

By changing the comparison routine, you can control whether data is sorted in ascending or descending order and other aspects of sorting. You can sort integers by value only, but you can sort strings by case-sensitive value, by case-insensitive value, by length, by the sums of the Roman numeral values of the characters, or by whatever you choose. To sort objects, you’ll probably want to compare based on a property such as size, color, name, position, or type.

The sort algorithm always works the same no matter what you’re sorting, but the compare operation varies. You need a way to combine a generic sort routine with a specific compare routine. The way to do this is to pass in a helper object that has Compare and Swap methods with the appropriate arguments (enforced through an interface). If you don’t like my Compare and Swap methods, define your own helper class. We’re going to get to helper classes in a moment. For now we’re interested only in the methods. For example, here’s
a very simple Compare method that sorts numeric data in ascending order:

Private Function ISortHelper_Compare(v1 As Variant, _
                                     v2 As Variant) As Integer
    If v1 < v2 Then
        ISortHelper_Compare = -1
    ElseIf v1 = v2 Then
        ISortHelper_Compare = 0
    Else
        ISortHelper_Compare = 1
    End If
End Function

You can compare numeric values (and non–case-sensitive strings) with relational operators. You return negative, zero, or positive (usually -1, 0, or 1), depending on whether the first value is less than, equal to, or greater than the second value. No matter how complex your comparison, only these three results are valid. (Ignore errors for now.) Incidentally, the Basic StrComp function works the same way, for the same reasons.

The SortArray sub uses Compare this way:

If .Compare(aTarget(iFirst), aTarget(iLast)) > 0 Then
    .Swap aTarget(iFirst), aTarget(iLast)
End If

Because this code simply checks to see whether the value is greater than 0, Compare could still work if it returned only 1 and 0. Comparison routines are also used by search routines (as you’ll see in “Binary Search,” page 295), and these routines must be able to distinguish all three results.

Here’s a specific Compare function from the CSortHelper class (SORTHELP.CLS):

Private Function ISortHelper_Compare(v1 As Variant, _
                                     v2 As Variant) As Integer
    ‘ Use string comparisons only on strings
    If TypeName(v1) <> “String” Then esmMode = esmSortVal
    
    Dim i As Integer
    Select Case esmMode
    ‘ Sort by value (same as esmSortBin for strings)
    Case esmSortVal
        If v1 < v2 Then
            i = -1
        ElseIf v1 = v2 Then
            i = 0
        Else
            i = 1
        End If
    ‘ Sort case-insensitive
    Case esmSortText
        i = StrComp(v1, v2, 1)
    ‘ Sort case-sensitive
    Case esmSortbin
        i = StrComp(v1, v2, 0)
    ‘ Sort by string length
    Case esmSortLen
        If Len(v1) = Len(v2) Then
            If v1 = v2 Then
                i = 0
            ElseIf v1 < v2 Then
                i = -1
            Else
                i = 1
            End If
        ElseIf Len(v1) < Len(v2) Then
            i = -1
        Else
            i = 1
        End If
    End Select
    If fHiToLo Then i = -i
    ISortHelper_Compare = i
End Function

This code tests the private class variables esmMode (of Enum type ESortMode) and fHiToLo.

Swapping presents similar problems. To swap data, you simply assign the first element to a temporary variable, assign the second element to the first, and assign the temporary variable to the second. Here’s the default swap routine for SortArray:

Private Sub ISortHelper_Swap(v1 As Variant, v2 As Variant)
    Dim vT As Variant
    vT = v1
    v1 = v2
    v2 = vT
End Sub

This works well for simple types, but if you’re swapping objects, files, or some other data, you’ll probably need a different swap routine. For example, if you were swapping files, you might want to simply swap the names rather than actually exchange all the data. Also, the sort, shuffle, and search procedures in this chapter will need a custom helper class to work with object variants. For one thing, you’ll need to use the Set statement to make assignments in the swap routines. For another, you’ll have to specify which properties to work on in the compare routines.