Henry, out of sheer curiosity, if you have a story of such evil follies I would be delighted to hear it. More seriously, do you have a tacit tail recursive verb for quicksort to share ? This is related to this post http://www.jsoftware.com/pipermail/programming/2014-August/039023.html
On Thu, Aug 28, 2014 at 9:18 PM, Henry Rich <[email protected]> wrote: > 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 > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
