Quicksort vs. Shell

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 

« Next Oldest  Next Newest »

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