Post Reply 
Quicksort vs. Shell
06-17-2014, 08:32 PM
Post: #13
RE: Quicksort vs. Shell
(06-17-2014 06:51 PM)Werner Wrote:  
(06-17-2014 06:07 PM)Claudio L. Wrote:  So log2(N) is a best-case scenario, N-1 is the worst-case, and in reality it's somewhere in between. Even with more advanced pivot picking techniques, there's always the chance that a wickedly-sorted list makes you hit the worst case.
If you sort 100 registers, and happen to hit the worst case, you'll need 99*sizeof(int)*(1+3) (assuming 1 for return address, and 3 arguments, but your implementation could have just 2 arguments), which is less than 1600 bytes. Your 4 kbytes of stack should be plenty.

Claudio

At every step you split the set in two halves, and if you sort the smaller half first you'll need at most log2(N) stack size.
Werner

Yes, I just read about that trick a few moments ago. It's also recommended not to recurse the second half, but do a tail call, so no stack is used. So it's not so bad after all, I can live with log2(N). I'll give it a shot.
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)