3 ms·
So, what's the right answer, guys? Quicksort? Radix?
by aston 19y ago
So, what's the right answer, guys? Quicksort? Radix?
- jey 19y agoWhen in doubt, use quantum bogosort. http://en.wikipedia.org/wiki/Bogosort#Quantum_Bogosort http://en.wikipedia.org/wiki/Bogosort#Quantum_Bogosort
- jraines 19y ago"There is also no telling how much processing power and/or memory would be required to destroy a universe." With my quad-core all I could manage was a thunderstorm in Denmark.
- dfranke 19y agoI prefer to use my cycles for good rather than evil. For example, my 8-core system is keeping me cozily warm throughout the presently-occuring snowstorm.
- tlrobinson 19y agoAny of the non-comparison sorts (radix, bucket, etc) would be good since he specified the elements are integers.
- aston 19y agoNot necessarily. The problem's rather underconstrained, but under reasonable asusumptions about memory allocation, you might actually get better performance from a quick sort, since the algorithm works with a lot of locality. Although you'd be right in a strict theoretical sense, sure.
- Tichy 19y agoI don't think you can recommend Quicksort unless you know something about the distribution of the elements to be sorted, or am I mistaken. After all, Quicksort can be very slow under certain conditions.
- aston 19y agoQuicksort's worst case involves bad pivot picking. The randomized version pretty much makes that a non-issue unless you're incredibly unlucky. Even still, with median-of-medians you can guarantee a deterministic worst case of nlog(n), so that's not true.
- jey 19y agoYou can keep track of the performance of Quicksort then fallback to Insertion Sort if Quicksort is sucking. This is how std::sort() works in most C++ implementations.