1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
# Практикум №1 по СД, спец. ИС
## Функцията std::sort
`std::sort` е стандартна функция в C++, която се използва за сортиране на елементи от дадена колекция от данни. Тя е част от стандартната библиотека `<algorithm>`, която съдържа различни алгоритми за обработка на колекции от данни.
Най-често е имплементирана или чрез `Quick Sort`, или чрез алгоритъм, комбиниращ `Quick Sort`, `Heap Sort` (за който ще научите по-натам в курса) и `Insertion Sort`.
Декларация на функцията:
```c++
#include <algorithm>
template <class RandomIt>
void sort(RandomIt first, RandomIt last);
template <class RandomIt, class Compare>
void sort(RandomIt first, RandomIt last, Compare comp);
```
- `Параметри`:
- first: Итератор, указващ началото на колекцията елементи, които трябва да бъдат сортирани.
- last: Итератор, указващ края на колекцията елементи, които трябва да бъдат сортирани (сочи елементът след последния елемент в диапазона).
- comp (по избор): критерий за сортиране (по default се използва operator<).
- `Сложност`: std::sort има средна времева сложност O(n*log n), където n е броят на елементите, които искаме да бъдат сортирани.
- `In-Place`: std::sort не е in-place алгоритъм.
- `Stable`: std::sort не е стабилен алгоритъм.
- Пример с функция:
```c++
#include <iostream>
#include <algorithm>
#include <vector>
bool compareLastDigit(int a, int b) {
return (a % 10) < (b % 10);
}
int main() {
std::vector<int> v = {25, 42, 33, 14, 56};
std::sort(v.begin(), v.end(), compareLastDigit);
for (const int& n : v) {
std::cout << n << ' ';
}
return 0;
}
```
- Пример с **ламбда** функция:
```c++
#include <iostream>
#include <algorithm>
#include <vector>
struct PairOfInt {
int first;
int second;
};
int main() {
std::vector<PairOfInt> v = { {1, 2}, {2, 1}, {5, 7}, {3, 3}, {4, 3} };
std::sort(v.begin(), v.end(), [](const PairOfInt& lhs, const PairOfInt& rhs) { return lhs.second < rhs.second; });
for (const auto& n : v) {
std::cout << n.first << ' ' << n.second << std::endl;
}
return 0;
}
```
## Задачи и линк към методите на `std::vector`
- [**std::vector**](https://cplusplus.com/reference/vector/vector/)
- [**Линк към задачите**](https://leetcode.com/problem-list/an1ryio3/)
- [Линк към таблица с leetcode акаунти](https://docs.google.com/spreadsheets/d/1KVdic02U7f97GT2LFu67t9Z4NqyFLmCj1TjyYdrcLBE/edit?gid=0#gid=0)
|
