Quicksort vs. Shell

06222014, 02:11 AM
Post: #26




RE: Quicksort vs. Shell
(06212014 02:32 PM)Werner Wrote: In a situation where the bulk of the work is in the comparisons, binary insertion would take constant time, so I don't understand why it would be so much faster for a reversed list? Well, the way I implemented it is like this: You are in the middle of sorting, so you have several elements already sorted, and you are evaluating element An: A0 ... An1 , An , ... Unsorted ... The algorithm takes An, and it compares it with A0 (left of the interval), and if it's less, then it inserts the element at the beginning. If not, it compares with An1, and if it's bigger, then you leave it there. Only if it's less you start doing the bisection. So I did the left comparison first, this means on a reversed list, it simply does one comparison, and inserts the element at the beginning of the list. So it's reversing the list with N comparisons. I could've done the An1 comparison first, then it would've required 2N comparisons to do the reverselist case. That should explain why so fast. On the other hand, a list that's already sorted would needlessly do 2N comparisons, so for the final implementation I reversed it, now it does the An1 comparison first. Claudio 

« Next Oldest  Next Newest »

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