Question / Problem:

Sort Algorithm in WinWrap Basic

Answer / Solution:

The following is an implementation of the Quick Sort algorithm purely in WinWrap Basic. It can be used to sort any type of object array. The example below sorts any array of Alternatives based on their confidence. And yes it is fast — it takes milliseconds to sort 100 items.

The concrete example below was a postprocessing of Database Locator results — where the alternative confidences where changed by script, and the alternatives needed resorting.

Preparing CscXDocFieldAlternatives for Sorting

This code snippet shows how to prepare CscXDocFieldAlternatives for sorting, call the sort routine, and then apply the changes to CscXDocFieldAlternatives.

Type alt
id As Integer
conf As Double
End Type
Public Sub resortAlternativesByConfidence(alts As CscXDocFieldAlternatives)
Dim i As Integer
'Create a list of references to alternatives to store their id and confidence.
' We will then sort the list by the confidence.
Dim refs() As alt
ReDim refs(alts.Count - 1)
For i = 0 To alts.Count - 1
refs(i).ID = i
refs(i).Conf = alts(i).Confidence
Next
sort(refs)
'Copy all of the resorted alternatives to the end of the Alternatives object
For i = 0 To alts.Count - 1
alts.Create()
altcopy(alts(refs(i).ID), alts(alts.Count - 1))
Next
'Delete all of the unsorted alternatives.
For i = alts.Count / 2 - 1 To 0 Step -1
alts.Remove(i)
Next
End Sub
'!!!!!! You MUST implement a Compare function for the sort algorithm to use.
'Here we sort based on confidence.
Private Function Compare(a As Variant, b As Variant)
If a.Conf > b.Conf Then Compare = True Else Compare = False
End Function

Quick Sort in WinWrap

This is the actual generic Quick Sort routine, which uses partitioning and recursion to sort:

Private Sub sort(ByRef a As Variant)
    quicksort(a, 0, UBound(a))
End Sub

Sub quicksort(ByRef a As Variant, ByVal Left As Integer, ByVal Right As Integer)
    Dim pivot As Integer
    If Right > Left Then
        pivot = getpivot(Left, Right)
        pivot = partition(a, Left, Right, pivot)
        quicksort(a, Left, pivot)
        quicksort(a, pivot + 1, Right)
    End If
End Sub

Function getpivot(ByVal Left As Integer, ByVal Right As Integer)
    'Return a random integer between Left and Right
    getpivot = (Rnd() * (Right - Left + 1) * 1000) Mod (Right - Left + 1) + Left
End Function

Function partition(ByRef a As Variant, ByVal Left As Integer, _
                            ByVal Right As Integer, ByRef pivot As Integer)

    Dim i
    Dim piv
    Dim store

    piv = a(pivot)
    swap(a(Right), a(pivot))
        store = Left
    For i = Left To Right - 1
        If Compare(a(i), piv) Then
            swap(a(store), a(i))
            store = store + 1
        End If
    Next
    swap(a(Right), a(store))
    partition = store
End Function

Sub swap(ByRef v1, ByRef v2)
    Dim tmp As Variant
    tmp = v1
    v1 = v2
    v2 = tmp
End Sub