Skip to content

Instantly share code, notes, and snippets.

Created June 29, 2012 16:25
Show Gist options
  • Save Lokutus/3018969 to your computer and use it in GitHub Desktop.
Save Lokutus/3018969 to your computer and use it in GitHub Desktop.
ArraySortProvider (non-recursive quicksort)
Class ArraySortProvider
Non-recursive quicksort algorithm
Using custom stack object instead-of recursion
Must be non-recursive, for lotusscript recursion stack is limited by 200!
@author Jiri Krakora
@date 15.6.2012
@uses Stack
Dim array() As Integer
Dim i As Long
ReDim array(0)
For i = 0 To 32000
Let array(i) = Rnd() * 1000
ReDim Preserve array(UBound(array) + 1)
Dim sorter As New ArraySortProvider(array)
For i = 0 To 1000
Print sorter.SortedArray(i)
Public Class ArraySortProvider
Private oArray As Variant
Private oStack As Stack
There is dependency on array to be sorted
@param fixed or dynamic array of any primitive type - strings or numbers
Public Sub New(arr As Variant)
Dim l As Long
Dim r As Long
Dim dt As Integer
Set Me.oStack = New Stack(0)
Let dt = DataType(arr)
If dt > 8000 Then
Let Me.oArray = arr
Let l = LBound(oArray)
Let r = UBound(oArray)
Call Me.Quicksort(l, r)
Let Me.oArray = Evaluate(|""|)
End If
End Sub
Public Property Get SortedArray As Variant
Let SortedArray = Me.oArray
End Property
Public Property Get UpperBound As Integer
Let UpperBound = UBound(Me.oArray)
End Property
Non-Recursive function for sorting
@param array to be sorted
@param left bound to start from
@param right bound to end with
Private Sub Quicksort(ByVal l As Long, ByVal r As Long)
Dim pivot As Long
Call Me.oStack.Push(l)
Call Me.oStack.Push(r)
While Not Me.oStack.IsEmpty
Let r = Me.oStack.Pop()
Let l = Me.oStack.Pop()
If r > l Then
Let pivot = Me.SetPivot(l, r)
' sort left side from pivot
Call Me.oStack.Push(l)
Call Me.oStack.Push(pivot)
' sort right side from pivot
Call Me.oStack.Push(pivot + 1)
Call Me.oStack.Push(r)
End If
End Sub
Set pivot position between smaller items on the left and larger on the right
@param left bound of the items array
@return right bound of the items array
Private Function SetPivot(l As Long, r As Long) As Long
Dim i As Long
Dim boundary As Long
Let boundary = l
' get boundary position for pivot
For i = l + 1 To r
If Me.oArray(i) < Me.oArray(l) Then
Let boundary = boundary + 1
Call Swap(i, boundary)
End If
' set pivot as a boundary
Call Me.Swap(l, boundary)
Let SetPivot = boundary
End Function
Swap two values in the array
@param array to be sorted
@param left position
@param right position
Private Sub Swap(l As Long, r As Long)
Dim tmp As Variant
Let tmp = Me.oArray(r)
Let Me.oArray(r) = Me.oArray(l)
Let Me.oArray(l) = tmp
End Sub
End Class
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment