G
Guest
hi everybod
I have used the usual Quicksort algorithm in Excel 2000 VBA (XPP, 512Mb RAM). Unfortunately, I get "Run-time error '28': Out of stack space" when recursion depth reaches about 10k to 20k (I've tried to sort an array of length 10k - not really big). I don't think I'm allocating to many variables (I understand 'byref' is default), I think the problem is simply the depth of the recursion and how it is handled by VBA. The code works fine for an array of length 1000 and I'm pretty sure the logic is right. MS Knowledge Base tells me to use loops... I don't think that's a good idea in this case. Does anybody have a workaround or some general information about recursions under VBA
(I'm not a programmer, so please use 'simple language'
Here's the code
'--------------------------------------------------
Sub Test(
Const n = 1000
Dim
Dim i As Lon
ReDim A(n - 1) As Doubl
For i = 0 To n -
A(i) = Sin(i
Nex
A = Quicksort(A, 0, n - 1
End Su
'-------------------------------------------------------------------------------
Function Quicksort(A As Variant, p As Long, r As Long) As Varian
'PRE: Array A, startindex p, lastindex
'POST: [p .. r] is sorte
'performance: average nLog(n), worst n^2, especially n^2 for sorted input (increasing or decreasing
Static q As Lon
If p < r The
q = Partition(A, p, r
A = Quicksort(A, p, q
A = Quicksort(A, q + 1, r
End I
Quicksort =
End Functio
'---------------------------------------------------------------
Function Partition(A As Variant, p As Long, r As Long
'PRE: Array A, startindex p, lastindex
'POST: index for Quicksort partitionin
Static pivot As Varian
Static tmp As Variant 'for swa
Static i As Long 'lower tracing inde
Static j As Long 'upper tracing inde
pivot = A(p
i = p -
j = r +
Do While Tru
D
j = j -
Loop Until A(j) <= pivo
D
i = i +
Loop Until A(i) >= pivo
If i < j Then 'swap A(j),A(i) and loo
tmp = A(j
A(j) = A(i
A(i) = tm
Els
Partition =
Exit Functio
End I
Loo
End Functio
'---------------------------------------------------------
Thank you for any comments.
I have used the usual Quicksort algorithm in Excel 2000 VBA (XPP, 512Mb RAM). Unfortunately, I get "Run-time error '28': Out of stack space" when recursion depth reaches about 10k to 20k (I've tried to sort an array of length 10k - not really big). I don't think I'm allocating to many variables (I understand 'byref' is default), I think the problem is simply the depth of the recursion and how it is handled by VBA. The code works fine for an array of length 1000 and I'm pretty sure the logic is right. MS Knowledge Base tells me to use loops... I don't think that's a good idea in this case. Does anybody have a workaround or some general information about recursions under VBA
(I'm not a programmer, so please use 'simple language'
Here's the code
'--------------------------------------------------
Sub Test(
Const n = 1000
Dim
Dim i As Lon
ReDim A(n - 1) As Doubl
For i = 0 To n -
A(i) = Sin(i
Nex
A = Quicksort(A, 0, n - 1
End Su
'-------------------------------------------------------------------------------
Function Quicksort(A As Variant, p As Long, r As Long) As Varian
'PRE: Array A, startindex p, lastindex
'POST: [p .. r] is sorte
'performance: average nLog(n), worst n^2, especially n^2 for sorted input (increasing or decreasing
Static q As Lon
If p < r The
q = Partition(A, p, r
A = Quicksort(A, p, q
A = Quicksort(A, q + 1, r
End I
Quicksort =
End Functio
'---------------------------------------------------------------
Function Partition(A As Variant, p As Long, r As Long
'PRE: Array A, startindex p, lastindex
'POST: index for Quicksort partitionin
Static pivot As Varian
Static tmp As Variant 'for swa
Static i As Long 'lower tracing inde
Static j As Long 'upper tracing inde
pivot = A(p
i = p -
j = r +
Do While Tru
D
j = j -
Loop Until A(j) <= pivo
D
i = i +
Loop Until A(i) >= pivo
If i < j Then 'swap A(j),A(i) and loo
tmp = A(j
A(j) = A(i
A(i) = tm
Els
Partition =
Exit Functio
End I
Loo
End Functio
'---------------------------------------------------------
Thank you for any comments.