Avijit_Chowdhury's blog

Sorting
By Avijit_Chowdhury, history, 2 years ago, In English

tell me if sorting is possible with O(n) time complexity???

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Counting sort: https://en.wikipedia.org/wiki/Counting_sort

→ Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Yes, with counting sort algorithm.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here lies your answer

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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.

→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In competitive programming you should not waste time on implementing sorting algorithms, instead use inbuilt STL sort function.

Complexity
Exception
Similar STL sorting functions

For implementation you may prefer to This

→ Reply