Skip to content

Instantly share code, notes, and snippets.

@Lokutus
Created June 29, 2012 16:24
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Lokutus/3018964 to your computer and use it in GitHub Desktop.
ArraySorter (recursive quicksort)
%REM
Class ArraySorter
Simple class to sort an array using recursive QuickSort
For bigger collections use ArraySortProvider
@author Jiri Krakora
@date 13.6.2012
@version 1.00
@uses
@revision
EXAMPLE:
----------------------------------------------------------------------------
Dim array(5) As Integer
Let array(0) = 7
Let array(1) = 3
Let array(2) = 8
Let array(3) = 9
Let array(4) = 2
Let array(5) = 1
Dim sorter As New ArraySorter(array)
Dim i As Long
For i = 0 To sorter.UpperBound
Print sorter.SortedArray(i)
Next
OUTPUT:
1
2
3
7
8
9
%END REM
Public Class ArraySorter
Private oArray As Variant
%REM
There is dependency on array to be sorted
@param fixed or dynamic array of any primitive type - strings or numbers
%END REM
Public Sub New(arr As Variant)
Dim l As Long
Dim r As Long
Dim dt As Integer
Let dt = DataType(arr)
If dt > 8000 Then
Let Me.oArray = arr
Let l = LBound(oArray)
Let r = UBound(oArray)
Call Me.Quicksort(Me.oArray, l, r)
Else
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
%REM
Recursive function for sorting
@param array to be sorted
@param left bound to start from
@param right bound to end with
%END REM
Private Sub Quicksort(array As Variant, l As Long, r As Long)
Dim i As Long
Dim boundary As Long
If l < r Then
Let boundary = l
' get boundary position for pivot
For i = l + 1 To r
If array(i) < array(l) Then
Let boundary = boundary + 1
Call Swap(array, i, boundary)
End If
Next
' set pivot as a boundary
Call Me.Swap(array, l, boundary)
' sort left part (smaller) of the array
Call Quicksort(array, l, boundary)
' sort right part (greater) of the array
Call Quicksort(array, boundary + 1, r)
End If
End Sub
%REM
Swap two values in the array
@param array to be sorted
@param left position
@param right position
%END REM
Private Sub Swap(array As Variant, l As Long, r As Long)
Dim tmp As Variant
Let tmp = array(r)
Let array(r) = array(l)
Let array(l) = tmp
End Sub
End Class
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment