Sorting: Difference between revisions
Jump to navigation
Jump to search
(Created page with "<!-- Sorting based on comparison is O(n lg n) at best - the work you end up doing in near-best cases is roughly N!/n^2 (which is roughly equal to n lg n), a figure related t...") |
mNo edit summary |
||
| Line 2: | Line 2: | ||
For sorting based on comparison, the work you end up doing in near-best cases is roughly N!/n^2 (which is roughly the same as O(n lg n)), a figure related to the amount of possible permutations (factorial; N!) and the amount of distinctions/divided subproblems - the good sorters are essentially divide-and-conquer that give an exponential division of work (exponential; 2^n). | |||
Comparison-based sorting is also very general, and simple to apply; mergesort and quicksort are close to this theorhetical minimum (in the average case, n^2 in the pretty much non-existant worst case), and properties like stable (for mergesort?{{verify}}) and in place (for quicksort?{{verify}}) can be provided. | Comparison-based sorting is also very general, and simple to apply; mergesort and quicksort are close to this theorhetical minimum (in the average case, n^2 in the pretty much non-existant worst case), and properties like stable (for mergesort?{{verify}}) and in place (for quicksort?{{verify}}) can be provided. | ||
Faster searches (theorhetically linear time) are possible, but only under very specific conditions (radix sort and counting sort | Faster searches (theorhetically linear time) are possible, but only under very specific conditions. | ||
You need some pretty specific fine-grained knowledge about the data that | |||
you need for nearly-free or things may amount to O(n lg n) anyway {{verify}} | |||
and when specific requirements are not met you cannot do them at all (e.g. radix sort and counting sort 's range limitation) and have to fall back to something else. | |||
It just doesn't work for general-purpose solutions, and don't even apply to a whole bunch of specific real-world cases. | |||
You need some pretty specific fine-grained knowledge about the data that, unless you get it for free, means the process as a whole is probably O(n lg n) or so. {{verify}} | |||