Domino Code Fragment

Code Name*
QuickSort		Date*
8/24/98		Source (or email address if you prefer)*
Lotus
IP address:.3.17.28.48
Description*
Sorts any array via a combination of Insertion Sort and Quicksort.		Type*
LotusScript		Categories*
List Processing/Sorting
Implementation:
None (plug and play)		Required Client:
4.0		Server:
Limitations:
Comments:
Example: mySortedArray = QuickSort(myArray)
Files/Graphics attachments (if applicable): Code:
Public Function QuickSort(sArray As Variant) As Variant
    Dim sA() As String    
    Dim j As Long
    Dim bottom As Long
    Dim top As Long
    bottom = Lbound ( sArray )
    top = Ubound ( sArray )
    Redim sA( bottom To top ) As String    
    For j = bottom To top
         sA ( j ) = sArray ( j )
    Next
    ' DoQS does a QuickSort if the Sublist is longer than 10 elements
    ' Thus, when DoQS finishes, all elements are within 10 spots of their correct location.
    ' For lists that are close to being in order, an Insertion Sort is much faster than a QuickSort, so we
    ' run through the whole thing once doing an Insertion Sort to finish tidying up the order.
    Call DoQS( sA, bottom, top )
    Call DoInsertSort ( sA, bottom, top )
    QuickSort = sA
End Function

Sub DoQS( sA() As String, bottom As Long, top As Long )
    ' Called by QuickSort
    ' Uses Public variable sA  (array of string)
    Dim length As Long
    Dim i As Long
    Dim j As Long
    Dim Pivot As Long
    Dim PivotValue As String
    Dim t As String
    Dim LastSmall As Long
    length = top - bottom + 1
   
    ' Only do the QuickSort if the sublist is at least 10 items long
    If length > 10 Then
         ' Pivot is chosen approx. halfway through sublist.
         ' This gives us best speed if list is almost sorted already, and is no worse than any
         ' other choice if the list is in random order.
         Pivot = bottom + (length \ 2)  
         
         ' Move PivotValue out of the way
         PivotValue = sA( Pivot )
         sA ( Pivot ) = sA ( bottom )
         sA ( bottom ) = PivotValue
         
         ' LastSmall is the location of the last value smaller than PivotValue
         LastSmall = bottom
         For i = bottom + 1 To top
              If sA ( i ) < PivotValue Then
                    LastSmall = LastSmall + 1
                   t = sA ( i )
                   sA ( i ) = sA ( LastSmall )
                   sA ( LastSmall ) = t
              End If
         Next
         
         ' Move the PivotValue back
         t = sA ( LastSmall )
         sA ( LastSmall ) = sA ( bottom )
         sA ( bottom ) = t
         Pivot = LastSmall
         
         ' Now sort each side
         Call DoQS ( sA, bottom, Pivot - 1 )
         Call DoQS ( sA, Pivot + 1, top )
    End If
End Sub

Sub DoInsertSort ( sA() As String, Byval bottom As Long, Byval top As Long )
    Dim i As Long
    Dim j As Long
    Dim t As String
    Dim Found As Integer
    For i = bottom + 2 To top
         If sA ( i ) < sA ( i - 1 ) Then
              j = i
              t = sA (i )
              Do
                   j = j - 1
                   sA ( j + 1 ) = sA ( j )
                   If j = 1 Then
                        Found = True
                   Else
                        Found = ( sA ( j - 1 ) <= t )
                   End If
              Loop Until Found
              sA ( j ) = t
         End If
    Next
End Sub