SsToRR's blog

Is std::sort enough?
By SsToRR, history, 22 months ago, In English

Is sorting algorithm in C++ library enough? What are the advantages of bubble sorting, merge sorting, or quick sorting? Do you need to know them for example for the national olympiad?

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

»
22 months ago, # |
  Vote: I like it +27 Vote: I do not like it

NO

→ Reply
»
22 months ago, # |
  Vote: I like it +20 Vote: I do not like it

I mostly agree with the previous comment but I'll give a more detail answer.
You will need to know about complexity
Bubble sorting and Insert sorting are dumb sortings they are in O(n^2), if you use them there is a big risk of Time limit excess
Smart sortings like merge and quick are O(nlog(n)) like the sort() of C++, it can be proved that no general comparisons based sort can go faster asymptotically (basicaly you can divide time by a constant but not more and I'd be amazed if you achieved to go faster than sort())
That being said there is counting sort (and bucket sort) that are kind of O(n), but they work with integer or the possibility to cut the value in buckets of size approximately n.
About knowing, I'd say don't start by learning them (start with binary search, graph traversal, two pointers, dp and general training).
But when you reach cyan, learn them, the idea can be reused elsewhere especially in interactive problem and a data-structure is linked to merge sorting.
Also quick sort is pretty straightforward as soon as you understand binary search

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Learn them! Here's a nice video which you will enjoy. https://youtube.com/watch?v=es2T6KY45cA&si=EnSIkaIECMiOmarE

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i think to know what does sort do and what does stable_sort do is also necessary.

→ Reply
»
22 months ago, # |
  Vote: I like it -16 Vote: I do not like it

No, because i might be hacked sometimes

→ Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Bubble sort is kind of interesting because there are some hard problems that utilize the algorithm’s monovariant (each element can be moved at most one position to the left in each iteration).

→ Reply