lang/C/sorting.and.searching.cormen.algo/src/vss.txt

   1
   2 ' shell sort
   3
   4 Private Function ShellSeq(ByRef h() As Long, ByVal n As Long)
   5     ' establish increment sequence (see Knuth, Vol 3)
   6     Dim p1 As Long
   7     Dim p2 As Long
   8     Dim p3 As Long
   9     Dim s As Long
  10     p1 = 1
  11     p2 = 1
  12     p3 = 1
  13     s = -1
  14     Do
  15         s = s + 1
  16         If s Mod 2 Then
  17             h(s) = 8 * p1 - 6 * p2 + 1
  18         Else
  19             h(s) = 9 * p1 - 9 * p3 + 1
  20             p2 = 2 * p2
  21             p3 = 2 * p3
  22         End If
  23         p1 = 2 * p1
  24     Loop While 3 * h(s) < n
  25
  26     If s > 0 Then s = s - 1
  27     ShellSeq = s
  28 End Function
  29
  30 Public Sub ShellSort(ByRef A() As Variant, ByVal Lb As Long, ByVal Ub As Long)
  31     Dim n As Long
  32     Dim h As Long
  33     Dim i As Long
  34     Dim j As Long
  35     Dim s As Long
  36     Dim t As Variant
  37     Dim seq(28) As Long
  38
  39     ' sort array[lb..ub]
  40     s = ShellSeq(seq, Ub - Lb + 1)
  41
  42     Do While s >= 0
  43         ' sort by insertion in increments of h
  44         h = seq(s)
  45         For i = Lb + h To Ub
  46             t = A(i)
  47             For j = i - h To Lb Step -h
  48                 If A(j) <= t Then Exit For
  49                 A(j + h) = A(j)
  50             Next j
  51             A(j + h) = t
  52         Next i
  53         s = s - 1
  54     Loop
  55 End Sub