C/sorting.and.searching.cormen.algo/src/vsq1.txt

   1
   2 ' quick sort
   3
   4 Private Function Partition(ByRef A() As Variant, ByVal Lb As Long, ByVal Ub As Long) _
   5         As Long
   6     Dim t As Variant
   7     Dim pivot As Variant
   8     Dim i As Long
   9     Dim j As Long
  10     Dim p As Long
  11
  12     ' partition array[lb..ub]
  13
  14     ' select pivot and exchange with 1st element
  15     p = Lb + (Ub - Lb) \ 2
  16     pivot = A(p)
  17     A(p) = A(Lb)
  18
  19     ' sort Lb+1 .. Ub based on pivot
  20     i = Lb
  21     j = Ub + 1
  22     Do
  23         Do
  24             j = j - 1
  25         While j > i And A(j) > pivot
  26         Do
  27             i = i + 1
  28         While i < j And A(i) < pivot
  29
  30         If i >= j Then Exit Do
  31
  32         ' swap A(i), A(j)
  33         t = A(i)
  34         A(i) = A(j)
  35         A(j) = t
  36     Loop
  37
  38     ' pivot belongs in A(j)
  39     A(Lb) = A(j)
  40     A(j) = pivot
  41     Partition = j
  42 End Function
  43
  44 Public Sub QuickSort(ByRef A() As Variant, ByVal Lb As Long, ByVal Ub As Long)
  45     Dim m As Long
  46
  47     ' sort array A(lb..ub)
  48
  49     Do While Lb < Ub
  50         ' quickly sort short lists
  51         If (Ub - Lb <= 12) Then
  52             Call InsertSort(A, Lb, Ub)
  53             Exit Sub
  54         End If
  55
  56         ' partition into two segments
  57         m = Partition(A, Lb, Ub)
  58
  59         ' sort the smallest partition to minimize stack requirements
  60         If m - Lb <= Ub - m Then
  61             Call QuickSort(A, Lb, m - 1)
  62             Lb = m + 1
  63         Else
  64             Call QuickSort(A, m + 1, Ub)
  65             Ub = m - 1
  66         End If
  67     Loop
  68 End Sub