Timeline for What is a the fastest sorting algorithm for an array of integers?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 20, 2015 at 17:12 | comment | added | D.W.♦ | @DavidRicherby, looking back at this after a year and a half, I agree with you. Thank you. | |
| Sep 20, 2015 at 10:46 | comment | added | David Richerby | @D.W. "Radix-sort is a general-purpose sorting algorithm (assuming you are sorting fixed-width integers)." Having to assume that you are sorting some restricted class of objects is the exact opposite of being general-purpose! | |
| Dec 4, 2013 at 19:18 | comment | added | rla4 | @D.W.: Radix sort should not be considered a 'general purpose' sorting algorithm, for it requires fixed length integer keys; is it not useful otherwise. But I get your point. :) I guess my mistake was focusing on sorting aything that could be compared, instead of sorting integers, specifically. They are different problems, and have a different set of possible solutions. The question does mention "a random array of integers", but I admit I took it as an example, rather than a restriction. | |
| Dec 3, 2013 at 22:08 | comment | added | Raphael | @D.W.: Of course, radix sort is only linear-time in well-chosen computational models, i.e. uniform cost model. This applies in practice only if keys are small (i.e. few). | |
| Dec 3, 2013 at 19:50 | history | edited | rla4 | CC BY-SA 3.0 |
added 9 characters in body
|
| Dec 3, 2013 at 18:03 | comment | added | gen | @rla4 sorry to see the downvote, your answer is one of the most helpful for me ;) | |
| Dec 3, 2013 at 17:04 | comment | added | rla4 | That's true, of course. I should have been more specific, thanks for pointing it out. However, I was a bit curious on which other sorting approaches (not comparison-based) you were referring to; Radix Sort is exactly the kind of O(n) algorithm I was talking about - you have to 'assume' something about the input (fixed-width integers). In this sense, it is not a general-purpose sorting algorithm, right? | |
| Dec 3, 2013 at 16:55 | comment | added | Patrick87 | Depends on what you mean by the sorting problem. General-purpose comparison-based sorts are not the only kind of sorting problems people have. | |
| Dec 3, 2013 at 16:50 | comment | added | D.W.♦ | This answer is not quite right. $\Omega(n \log n)$ is not a universal lower bound for sorting. That lower bound only applies to comparison-based sorts, i.e., sorting algorithms that use only comparisons. Some sorting algorithms are not comparison-based. The statement "There are some algorithms that perform sorting in O(n), but they all rely on making assumptions about the input, and are not general purpose sorting algorithms." might be a little misleading -- be careful. Radix-sort is a general-purpose sorting algorithm (assuming you are sorting fixed-width integers). | |
| Dec 3, 2013 at 14:42 | history | edited | Guy Coder | CC BY-SA 3.0 |
Use blockquote and link.
|
| Dec 3, 2013 at 14:36 | review | First posts | |||
| Dec 3, 2013 at 14:42 | |||||
| Dec 3, 2013 at 14:19 | history | answered | rla4 | CC BY-SA 3.0 |