Code-a-holic: quick sort

Tuesday, September 27, 2005
[VBScript] allsorts (not licorice)

Assorted sorts. I figured out I didn't need them after all. The BubbleSort is the slowest on large datasets.
Sub BubbleSort( arr )
    dim arr_j, arr_j1, i, j, temp
    for i = UBound(arr) - 1 To 0 Step -1
        for j = 0 to i
            arr_j = arr( j )
            arr_j1 = arr( j + 1 )
            if arr_j > arr_j1 then
                temp=arr_j1
                arr(j+1)=arr_j
                arr(j)=temp
            end if
        next
    next
End Sub


Sub QuickSort(vec,loBound,hiBound)
  Dim pivot,loSwap,hiSwap,temp


  '== This procedure is adapted from the algorithm given in:
  '==    Data Abstractions & Structures using C++ by
  '==    Mark Headington and David Riley, pg. 586
  '== Quicksort is the fastest array sorting routine for
  '== unordered arrays.  Its big O is  n log n


    '~ http://4guysfromrolla.com/webtech/012799-2.shtml


  '== Two items to sort
  if hiBound - loBound = 1 then
    if vec(loBound) > vec(hiBound) then
      temp=vec(loBound)
      vec(loBound) = vec(hiBound)
      vec(hiBound) = temp
    End If
  End If


  '== Three or more items to sort
  pivot = vec(int((loBound + hiBound) / 2))
  vec(int((loBound + hiBound) / 2)) = vec(loBound)
  vec(loBound) = pivot
  loSwap = loBound + 1
  hiSwap = hiBound


  do
    '== Find the right loSwap
    while loSwap < hiSwap and vec(loSwap) <= pivot
      loSwap = loSwap + 1
    wend
    '== Find the right hiSwap
    while vec(hiSwap) > pivot
      hiSwap = hiSwap - 1
    wend
    '== Swap values if loSwap is less then hiSwap
    if loSwap < hiSwap then
      temp = vec(loSwap)
      vec(loSwap) = vec(hiSwap)
      vec(hiSwap) = temp
    End If
  loop while loSwap < hiSwap


  vec(loBound) = vec(hiSwap)
  vec(hiSwap) = pivot


  '== Recursively call function .. the beauty of Quicksort
    '== 2 or more items in first section
    if loBound < (hiSwap - 1) then Call QuickSort(vec,loBound,hiSwap-1)
    '== 2 or more items in second section
    if hiSwap + 1 < hibound then Call QuickSort(vec,hiSwap+1,hiBound)


End Sub  'QuickSort


Function ShellSort( ArrayToSort )
    '~ http://www.adit.co.uk/html/a_question_of_sorts.html


    Dim SortLoop, ShellPoint
    Dim  HoldValue, SortPoint


   ShellPoint = Lbound(ArrayToSort)
   Do Until ShellPoint >  Ubound(ArrayToSort)
       ShellPoint = (3 *  ShellPoint) + 1
   Loop


   Do Until ShellPoint =  Lbound(ArrayToSort)
       ShellPoint = ShellPoint / 3
       For SortLoop = (ShellPoint + LBound(ArrayToSort)) To Ubound(ArrayToSort)
           HoldValue =  ArrayToSort(SortLoop)
           SortPoint = SortLoop
           Do While (ArrayToSort(SortPoint - ShellPoint) > HoldValue)
               ArrayToSort(SortPoint) = ArrayToSort(SortPoint - ShellPoint)
               SortPoint = SortPoint - ShellPoint
               If SortPoint < ShellPoint Then
                   Exit Do
               End If
           Loop
           ArrayToSort(SortPoint) = HoldValue
       Next
   Loop
   ShellSort = True
End Function