Post Reply 
Quicksort vs. Shell
06-17-2014, 09:45 PM
Post: #15
RE: Quicksort vs. Shell
(06-17-2014 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 worst-case of 999 times (less if it's the median-of-3 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 Smile 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
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
Quicksort vs. Shell - Claudio L. - 06-16-2014, 09:38 PM
RE: Quicksort vs. Shell - Paul Dale - 06-16-2014, 10:18 PM
RE: Quicksort vs. Shell - Brad Barton - 06-17-2014, 02:51 AM
RE: Quicksort vs. Shell - walter b - 06-17-2014, 06:24 AM
RE: Quicksort vs. Shell - BruceH - 07-11-2022, 10:15 PM
RE: Quicksort vs. Shell - Katie Wasserman - 06-17-2014, 04:25 AM
RE: Quicksort vs. Shell - Paul Dale - 06-17-2014, 05:22 AM
RE: Quicksort vs. Shell - Claudio L. - 06-17-2014, 03:03 PM
RE: Quicksort vs. Shell - Marcus von Cube - 06-17-2014, 05:12 PM
RE: Quicksort vs. Shell - Claudio L. - 06-17-2014, 06:07 PM
RE: Quicksort vs. Shell - Werner - 06-17-2014, 06:51 PM
RE: Quicksort vs. Shell - Claudio L. - 06-17-2014, 08:32 PM
RE: Quicksort vs. Shell - Paul Dale - 06-17-2014, 09:50 PM
RE: Quicksort vs. Shell - Werner - 06-17-2014, 06:53 PM
RE: Quicksort vs. Shell - Claudio L. - 06-17-2014, 09:15 PM
RE: Quicksort vs. Shell - Werner - 06-18-2014, 05:10 AM
RE: Quicksort vs. Shell - Paul Dale - 06-17-2014 09:45 PM
RE: Quicksort vs. Shell - Paul Dale - 06-17-2014, 10:02 PM
RE: Quicksort vs. Shell - Werner - 06-17-2014, 09:22 AM
RE: Quicksort vs. Shell - David Hayden - 06-18-2014, 12:27 PM
RE: Quicksort vs. Shell - Claudio L. - 06-18-2014, 04:29 PM
RE: Quicksort vs. Shell - Werner - 06-18-2014, 06:28 PM
RE: Quicksort vs. Shell - Claudio L. - 06-18-2014, 06:57 PM
RE: Quicksort vs. Shell - Namir - 06-19-2014, 12:44 AM
RE: Quicksort vs. Shell - Claudio L. - 06-20-2014, 02:12 PM
RE: Quicksort vs. Shell - Albert Chan - 07-10-2022, 06:20 PM
RE: Quicksort vs. Shell - Werner - 06-21-2014, 02:32 PM
RE: Quicksort vs. Shell - Claudio L. - 06-22-2014, 02:11 AM



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