In the case of quicksort, some implementations try to be clever/"efficient" by using the first or last item as the pivot point (instead of a random element). The evil people is most often yourself in this case as a previously sorted data (say in an other routine that needed it sorted) results in the worst possible quicksort performance.
----- Original Message ----- From: Henry Rich <[email protected]> To: [email protected] Cc: Sent: Thursday, August 28, 2014 9:18:31 PM Subject: Re: [Jprogramming] fit conjunction 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
