Timeline for Handling duplicate keys in quicksort
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 5, 2011 at 6:36 | comment | added | Derek | 3. I'm cool with that 5. I have a working heapsort, so introsort will be my next project. I'll test it against this quicksort and see what happens | |
| Aug 5, 2011 at 6:35 | vote | accept | Derek | ||
| Aug 5, 2011 at 6:22 | comment | added | Winston Ewert | @Derek, 3. This is code review, I reserve the right to complain that your code has been made less readable for probably undetectable performance gains. You can reserve the right to ignore me. :) 5. I'm not suggesting a better pivot selection algorithm. I'm wondering whether your strategy has any advantage over something like introsort. | |
| Aug 5, 2011 at 6:12 | comment | added | Derek | 1. OH RIGHT... I forgot about the other swaps... 3. The complexity of the code is of no concern, so long as I can understand it; I'm coding this for fun (yes, I do that) 5. I'm open to any pivot-selection algorithms; any one in particular that you recommend? | |
| Aug 5, 2011 at 6:07 | comment | added | Winston Ewert | @Derek, 1. you are still repeating the swap code three times. 3. There is also the while loop (which would be an if statement) but just generally your code obscures the nature of the quicksort algorithm. 5. Choosing a random pivot is good, but that doesn't guarantee you won't have problems. You could randomnly choose bad pivots. | |
| Aug 5, 2011 at 5:55 | comment | added | Derek | I don't know how to put newlines in comments... sorry 'bout that | |
| Aug 5, 2011 at 5:54 | comment | added | Derek | 1. I just changed the code inside the loop so that the lines aren't repeated. Is that better or worse than before? 2. Too lazy to do that now, but you're right 3. The added complexity doesn't seem like much to me; it's just one extra if-else statement 4. I like that way of handling duplicates, I'll implement it when it's not 2AM 5. I do choose a random pivot... the only more efficient pivot choices are the median-of-three (still no O(nlogn) guarantee) and the O(n) selection algorithms (these esnure O(nlogn) time but increase those pesky constant factors) | |
| Aug 5, 2011 at 5:43 | history | answered | Winston Ewert | CC BY-SA 3.0 |