Quicksort vs. Shell

06172014, 06:07 PM
Post: #10




RE: Quicksort vs. Shell
(06172014 05:12 PM)Marcus von Cube Wrote:(06172014 03:03 PM)Claudio L. Wrote: How did you manage the recursion part? Ideally, if you partition exactly in half every time, you get log2(N), but you don't know where your pivot falls within the list. If you have a list that's already sorted, and pick the last element as a pivot, for example, you get the worst case, where after each recursion, your partitions are not half the size, but merely (n1) elements on one side and zero in the other, with 'n'= size of the previous partition. So log2(N) is a bestcase scenario, N1 is the worstcase, and in reality it's somewhere in between. Even with more advanced pivot picking techniques, there's always the chance that a wickedlysorted 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. I'm thinking of using 4 kbytes of stack as well, but we have no plans to put a limit on the list size, so the possibility of stack overrun is always there. Claudio 

« Next Oldest  Next Newest »

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