tell me if sorting is possible with O(n) time complexity???
tell me if sorting is possible with O(n) time complexity???
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | BledDest | 145 |
Name |
---|
Counting sort: https://en.wikipedia.org/wiki/Counting_sort
Yes, with counting sort algorithm.
Here lies your answer
I'm pretty sure we've all heard that the best sorting worst-case scenario is $$$\mathcal{O} (N \log N)$$$. What people really mean is that the best comparison sort is worst case $$$\mathcal{O} (N \log N)$$$. Comparison sort basically means that we assume nothing about the items except that they can be compared with another via some oracle.
Indeed, one can prove straight-forwardly that the best comparison sort is worst-case $$$\mathcal{O} (N \log N)$$$. One can find a proper proof on the internet, but they way I think of it is that we have $$$N!$$$ permutations and by checking the relation between $$$u, v$$$, we halve the number of possible permutations. So we need $$$\log_2(N!) \approx N \log N$$$ "queries." Again, this is very crude, but I find it more intuitive than the pedantic proofs online.
Now, if you want to assume more than just "items can be compared," then yes, sorting can be done in $$$\mathcal{O}(N)$$$. This can be done using radix sort, for example, if you assume that keys can be partitioned into "boxes". If you assume further that the keys are small integers, then you can use counting sort, which is also $$$\mathcal{O}(N)$$$.
But personally, I think radix and counting sort are cheap :P.
The end of my sorting rant.
In competitive programming you should not waste time on implementing sorting algorithms, instead use inbuilt STL sort function.
On average, linearithmic in the distance between first and last: Performs approximately
N*log2(N)
(where N is this distance) comparisons of elements, and up to that many element swaps (or moves).Throws if any of the element comparisons, the element swaps (or moves) or the operations on iterators throws. Note that invalid arguments cause undefined behavior.
Stable Sort
Partial Sort
For implementation you may prefer to This