I decided to split this discussion from the other topic, when I realized just how off-topic I was going
original topic here:
http://www.computerhope.com/forum/index.php?action=post;topic=76208.15;num_replies=18As far as dev time is concerned, it is almost always easier for any non-trivial recursive algorithm (IE- mutual recursion or calling itself in multiple locations) to code the function recursively. For kicks I wrote an iterative version of Quicksort- for comparison here is the routine (VB6) that uses recursion:
Private Sub DoQuickSort(ByRef Arraysort() As Variant)
'quicksort algorithm:
Dim Lower() As Variant, Upper() As Variant, equal() As Variant
Dim Pivot As Variant, I As Long
Dim haslower As Boolean, hasupper As Boolean, hasequal As Boolean
Dim tmp As Variant, lowercount As Long, Uppercount As Long, equalcount As Long
Debug.Print "QuickSort: Size=" & Str$(UBound(Arraysort) - LBound(Arraysort))
'the quicksort algorithm chooses a pivot point.
'this pivot point is compared to all items in the array, with items
'that are less than the value moved into one array, and those that are larger into another.
'then, QuickSort recursively calls itself on these two arrays.
If UBound(Arraysort) - LBound(Arraysort) < 5 Then
'do a bubble.
DoBubbleSort Arraysort
Else
Pivot = QuickGetPivot(Arraysort, Lower, Upper)
For I = LBound(Arraysort) To UBound(Arraysort)
If CompareItems(Arraysort(I), Pivot) = -1 Then
ReDim Preserve Lower(lowercount)
Lower(lowercount) = Arraysort(I)
lowercount = lowercount + 1
haslower = True
ElseIf CompareItems(Arraysort(I), Pivot) = 0 Then
'equal
ReDim Preserve equal(equalcount)
equal(equalcount) = Arraysort(I)
equalcount = equalcount + 1
hasequal = True
Else
ReDim Preserve Upper(Uppercount)
Upper(Uppercount) = Arraysort(I)
Uppercount = Uppercount + 1
hasupper = True
End If
Next I
'recursively quicksort each half.
If haslower Then DoQuickSort Lower()
If hasupper Then DoQuickSort Upper()
'merge 'm.
ReDim Arraysort(LBound(Arraysort) To UBound(Arraysort))
If haslower Then
For I = 0 To UBound(Lower)
Arraysort(LBound(Arraysort) + I) = Lower(I)
Next I
End If
If hasequal Then
For I = 0 To UBound(equal)
Arraysort(LBound(Arraysort) + lowercount + I) = equal(I)
Next I
End If
If hasupper Then
For I = 0 To UBound(Upper)
Arraysort(LBound(Arraysort) + lowercount + equalcount + I) = Upper(I)
Next I
End If
Erase Lower
Erase Upper
End If
End Sub
Relatively short considering what it does- Ideally I would use another sorting algorithm for small arrays, but I omitted that here.
The iterative version was quite a bit different, since it uses a Interface for comparing two items, and also my DataStack Class, neither of which I will list due to size constraints
' Iterative QuickSort algorithm
#If VARIANTARR Then
Sub SortArray(aTarget() As Variant, Optional vFirst As Variant, _
Optional vLast As Variant, Optional SortHelper As ISortHelper = Nothing, Optional ByVal FlDescending As Boolean = False)
#Else
Sub SortArray(aTarget As Variant, Optional vFirst As Variant, _
Optional vLast As Variant, Optional SortHelper As ISortHelper = Nothing, Optional ByVal FlDescending As Boolean = False)
#End If
Dim iFirst As Long, iLast As Long
If IsMissing(vFirst) Then iFirst = LBound(aTarget) Else iFirst = vFirst
If IsMissing(vLast) Then iLast = UBound(aTarget) Else iLast = vLast
If SortHelper Is Nothing Then Set SortHelper = New CSortHelper
With SortHelper
Dim iLo As Long, iHi As Long, iRand As Long, stack As New DataStack
Do
Do
' Swap from ends until first and last meet in the middle
If iFirst < iLast Then
' If we're in the middle and out of order, swap
If iLast - iFirst = 1 Then
If .compare(aTarget(iFirst), aTarget(iLast), FlDescending) > 0 Then
.Swap aTarget(iFirst), aTarget(iLast)
End If
Else
' Split at some random point
.Swap aTarget(iLast), _
aTarget(Random(iFirst, iLast))
' Swap high values below the split for low values above
iLo = iFirst: iHi = iLast
Do
' Find any low value larger than split
Do While (iLo < iHi) And _
(.compare(aTarget(iLo), aTarget(iLast), FlDescending) <= 0)
iLo = iLo + 1
Loop
' Find any high value smaller than split
Do While (iHi > iLo) And _
(.compare(aTarget(iHi), aTarget(iLast), FlDescending) >= 0)
iHi = iHi - 1
Loop
' Swap too high low value for too low high value
If iLo < iHi Then .Swap aTarget(iLo), aTarget(iHi)
Loop While iLo < iHi
' Current (iLo) is larger than split (iLast), so swap
.Swap aTarget(iLo), aTarget(iLast)
' Push range markers of larger part for later sorting
If (iLo - iFirst) < (iLast - iLo) Then
stack.Push iLo + 1
stack.Push iLast
iLast = iLo - 1
Else
stack.Push iFirst
stack.Push iLo - 1
iFirst = iLo + 1
End If
' Exit from inner loop to process smaller part
Exit Do
End If
End If
' If stack empty, Exit outer loop
If stack.Count = 0 Then Exit Sub
' Else pop first and last from last deferred section
iLast = stack.Pop
iFirst = stack.Pop
Loop
Loop
End With
End Sub
the iterative version is longer, but uses up less stack space... (literally no stack space, really)
