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?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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?
Название |
---|
NO
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
Learn them! Here's a nice video which you will enjoy. https://youtube.com/watch?v=es2T6KY45cA&si=EnSIkaIECMiOmarE
i think to know what does sort do and what does stable_sort do is also necessary.
No, because i might be hacked sometimes
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).