Quicksort vs. Shell

06172014, 09:45 PM
Post: #15




RE: Quicksort vs. Shell
(06172014 03:03 PM)Claudio L. Wrote: How did you manage the recursion part? It isn't. Recursion is the naïve implementation. The amount of state required at each level is two indexes. Put these in an array instead. Quote:My main concern on using quicksort (besides the fact that it may be slower for some cases) is that it's recursive. Our C stack will be tiny and limited, ... As Marcus notes, we've got 4kb for the stack and an amount of global state (but not all of it). This is limited but still vastly more space than we need here. Vastly as in many orders of magnitude larger than needed  we could sort all digital memory on the planet with this space and still have headroom. Quote:If the list is already sorted, standard quicksort will recurse a worstcase of 999 times (less if it's the medianof3 version), needing about 16kbytes of RAM in the stack (assuming there's no local variables at all, just the return address saved and 3 arguments per call). The unnecessary extra state is exactly why quicksort shouldn't actually be implemented recursively in low memory environments. I'd almost go as far as saying it shouldn't be recursive in any environment. The important point you are missing is the worst case depth. As Marcus notes, this is indeed O(log n). Why? Remember that you have a choice as to which partition to sort first. Choose wisely and the worst case depth is guaranteed to be small. Quote:Heap sort is more complex than shell sort, and about the same performance, so it's not worth the effort. Unless you want a heap for something else. e.g. managing alarms is best done via a heap. Quote:That leaves us with Quicksort vs Shell, hence the title of this thread. Quicksort all the way The sorting wars of the 60s have been won. Quicksort was the victor. Pretty much everything uses a flavour of quicksort these days. Why the need for these questions? The 34S source code is available and a search for quicksort will find you the implementation.  Pauli 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)