Timeline for Why is quicksort better than other sorting algorithms in practice?
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 6, 2022 at 9:00 | history | tweeted | twitter.com/StackSoftEng/status/1600052445010345984 | ||
| Dec 5, 2022 at 23:41 | answer | added | gnasher729 | timeline score: 0 | |
| S Dec 5, 2022 at 22:52 | history | suggested | Simply Beautiful Art |
Added missing tag
|
|
| Nov 26, 2022 at 6:14 | review | Suggested edits | |||
| S Dec 5, 2022 at 22:52 | |||||
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Feb 26, 2016 at 11:08 | comment | added | Raphael | @SeasonalShot I'm shocked you did not read the accepted answer before commenting. | |
| Feb 26, 2016 at 7:37 | comment | added | SeasonalShot | I am shocked no one mentioned Timsort. | |
| Jun 5, 2012 at 11:01 | vote | accept | Raphael | ||
| Jun 1, 2012 at 20:38 | comment | added | Raphael | @mjgates: No, Quicksort does not have "exactly the same big-O characteristics as mergesort". As the question correctly states, worst-case complexity differs. | |
| Jun 1, 2012 at 16:33 | comment | added | mjfgates | Quicksort has exactly the same big-O characteristics as mergesort. It's usually considered "faster" than mergesort because it performs more comparisons than merge, but moves data items less often, and for MOST applications, moves are more expensive than compares. I once found myself using mergesort because I was comparing VARIANT structs, and doing the "moves" by swapping pointers in an array... | |
| May 30, 2012 at 14:59 | comment | added | Donal Fellows | The other question that should be asked is why merge sort is popular with library writers. The reason? It's not much slower than quicksort, and it's stable (which matters a lot when you end up resorting data, which is relatively common in practice). | |
| May 30, 2012 at 14:38 | answer | added | dr jimbob | timeline score: 23 | |
| May 29, 2012 at 17:20 | comment | added | Giorgio | @Raphael: Often what is called quick sort is actually some variation like intro sort (used, afaik, in the C++ standard library), not pure quick sort. | |
| May 29, 2012 at 16:38 | answer | added | comingstorm | timeline score: 1 | |
| May 29, 2012 at 14:18 | comment | added | RalphChapin | Someone has to say this for completeness, so I will: Quicksort is not (usually) stable. For this reason, you may not want to use it. Also, for this reason, your default sort may not be a Quicksort even when that is what you want. | |
| May 29, 2012 at 11:08 | answer | added | Doc Brown | timeline score: 16 | |
| May 29, 2012 at 10:46 | answer | added | vartec | timeline score: 7 | |
| May 29, 2012 at 10:24 | answer | added | Ramzi Kahil | timeline score: 18 | |
| May 29, 2012 at 10:23 | answer | added | James Anderson | timeline score: 5 | |
| May 29, 2012 at 10:15 | comment | added | Raphael | @DocBrown: Many Quicksort (or variants of it) implementations are chosen in many libraries, arguably because they perform best (I would hope so, that is). So there might just be something about the algorithm that makes Quicksort fast, independently of the implementation. | |
| May 29, 2012 at 9:42 | comment | added | Doc Brown | "why does quicksort outperform other sorting algorithms in practice?" Sure that's true? Show us the real implementation you are refererring to with this statement, and the community will tell you why that specific implementation behaves the way it does. Everything else will lead to wild guessing about non-existent programs. | |
| May 29, 2012 at 9:20 | comment | added | AProgrammer | Quicksort reputation dates from a time when cache didn't exist. | |
| May 29, 2012 at 8:58 | history | asked | Raphael | CC BY-SA 3.0 |