Re: Recursive functions and stack overload
Re: Recursive functions and stack overload
- Subject: Re: Recursive functions and stack overload
- From: Nicko van Someren <email@hidden>
- Date: Thu, 27 Apr 2006 08:54:36 +0100
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.
Nicko
_______________________________________________
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