On the contrary, stack depth is a killer for quicksort. In the worst
case, the stack depth is the number of items, as each partitioning gives
a partition of just one element. Tail recursion solves this problem.
Not likely, you say? If your code is deployed somewhere important, Evil
People will send it an array that will produce a worst case.
Perhaps you can use a random pivot... as long as the Evil People can't
guess your sequence.
Henry Rich
On 8/28/2014 9:13 PM, Raul Miller wrote:
I guess I'd like to see your code to better understand how you are thinking.
You might have a good point. You might be overlooking something. But I do
not know yet.
(This sounds fun, but stack depth is unlikely to be a problem for
quicksort. Also, quicksort is often overkill and /:~ or bare /: are also
worth considering.)
Thanks,
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
