Re: Recursive functions and stack overload
Re: Recursive functions and stack overload
- Subject: Re: Recursive functions and stack overload
- From: John Stiles <email@hidden>
- Date: Thu, 27 Apr 2006 10:38:11 -0700
On Apr 27, 2006, at 12:54 AM, Nicko van Someren wrote:
On 26 Apr 2006, at 22:53, Andrew Farmer wrote:
On 26 Apr 06, at 01:26, Paolo Bertani wrote:
I'm sorting a plain C array with the "Quicksort" algorithm.
The quicksort() function calls itself recursively for a numer of
times that depends on the size of the array and the array's
initial configuration.
Since the array contains 10,000-100,000 elements the function
calls itself many times.
Is there the risk of some sort of stack overload?
Not really.
Quicksort has a maximum stack depth of lg(n), where n is the
number of elements in the array. Even with a 100,000 element
array, the maximum recursion depth is 16-17 calls.
That's not true. Quicksort has an expected stack depth which is of
the order of log2(n) but the worst case has a stack depth of n (in
the pathological case that the 'pivot' is always the smallest or
largest). This is particularly an issue because the pathological
case WILL happen if you are naive about choosing your pivot and the
list is already sorted. In each iteration of the quicksort, if you
choose the first or last item in the range and the list is already
sorted then all the items in the range are either larger or
smaller, there is no 'divide and conquer' and you just trim one
item off the range before you go around again.
So, if you have built your own quicksort() function you might want
to add some code to watch the depth of recursion. If it's hitting
the pathological case then you might want to add something extra to
change the way that you pick your pivot value.
Actually, this is a solved problem; check out the "introsort"
algorithm (try Wikipedia). It is basically a modified quicksort which
guarantees a sane maximum recursion depth. It's the sort algorithm
used by most STL implementations (including GCC).
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden