Quicksort vs. Shell

06182014, 06:28 PM
Post: #21




RE: Quicksort vs. Shell
Yes, that's me alright.
I didn't change my mind  I said that in RPL, binary insertion is as good as it gets: few timeconsuming comparisions, and fast stack exchanges. In Saturn assembly, there's no match for the medianofthree Quicksort I used. It will sort just about anything you can throw at it, save units, and at a speed comparable to the best typededicated programs. And it's stable, by the way, using the very technique you described. I have a much more recent version (only a few months ago) lying around somewhere.. I think this one still has a bug, and won't do binary integers. I'll see if I can upload a version to hpcalc.org. Cheers, Werner 

06182014, 06:57 PM
Post: #22




RE: Quicksort vs. Shell
(06182014 06:28 PM)Werner Wrote: Yes, that's me alright. Thanks for your insight! Claudio 

06192014, 12:44 AM
Post: #23




RE: Quicksort vs. Shell
About 15 years ago I designed a "Modified CombSort Algorithm" by significantly enhancing the CombSort algorithm which itself is an enhancement of the slow Bubble Sort. You can find my article here.
Namir 

06202014, 02:12 PM
(This post was last modified: 06202014 02:21 PM by Claudio L..)
Post: #24




RE: Quicksort vs. Shell
I implemented all 3 methods for testing, since the answer wasn't clear after all the discussions.
I tested by sorting the same lists with 2, 4, 6, ... 1998 elements (tested on the PC, I might test on calc later just to get a feeling for the real timings). In the tests, I added significant overhead to the comparison, to make it similar to our use case. Results were: Fully random case: Binary insertion: 2.01 sec Shell sort: 2.12 sec Quicksort: 1.83 sec Reversed list: Binary insertion: 0.56 sec Shell sort: 1.67 sec Quicksort: 2.28 sec 90% sorted, 10% random: Binary insertion: 1.91 sec Shell sort: 2.02 sec Quicksort: 2.17 sec So in the end, binary sort beats shell sort (point for Werner, good call there). The fully random test is a bestcase for quicksort, but it only outruns binary insertion by 10%. Binary insertion shines on fully reversed lists, and both shell sort and binary sort can beat quicksort with almost sorted or reversed lists. So in the end, I think binary insertion is the method we'll use, since it's consistently fast, versus a quicksort that can fall down. For the record: I tuned each algorithm as follows:
EDIT: Sort was made stable for all methods using method described in a post above. Claudio 

06212014, 02:32 PM
Post: #25




RE: Quicksort vs. Shell
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?
Werner 

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 

07102022, 06:20 PM
Post: #27




RE: Quicksort vs. Shell
(06202014 02:12 PM)Claudio L. Wrote: EDIT: Sort was made stable for all methods using method described in a post above. What is the cost of making unstable sort stable? I assume comparisons now cost doubled. (L[i] < L[j]) → (L[i] < L[j] or (L[i]==L[j] and i<j)) Swapping elements may also cost more. Index had to carry along, to break ties if needed. swap(a[i], a[j]) → swap({a[i],i}, {a[j],j}) Another way to look at this, with index attached, all elements are different. Sort stability issue is now moot. 

07112022, 10:15 PM
Post: #28




RE: Quicksort vs. Shell
(06162014 10:18 PM)Paul Dale Wrote: There is always this sort. Nice. A close cousin of the Miracle Sort. 

« Next Oldest  Next Newest »

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