Add pract03 readme, merge and partition implementations

3 files changed, 230 insertions, 0 deletions

diff --git a/Practicum/pract03/README.md b/Practicum/pract03/README.md
new file mode 100644
index 0000000..528ce87
--- /dev/null
+++ b/Practicum/pract03/README.md
@@ -0,0 +1,100 @@
+# Практикум №3 по СД, спец. ИС
+
+## Задача 1
+Даден е вектор от думи, съставени изцяло от малки латински букви. Напишете програма, която пренарежда вектора така, че в началото да са всички думи, 
+започващи с буквата 'а', след тях -  тези, започващи с буквата 'b' и т.н. Алгоритъмът да работи in-place.
+
+***hint*** : търсим сложност Θ(n), където n е големината на масива.
+
+Пример:
+
+Вход:
+```
+words = {banana, apple, alpaca, cat, biscuit, elephant, string, house, progress, trousers, mouse}
+```
+
+Изход:
+```
+words = {apple, alpaca, banana, biscuit, cat, elephant, house, mouse, progress, string, trousers}
+```
+
+## Задача 2
+Дадени са два вектора от числа. Напишете програма, която връща нов вектор, който съдържа всички числа от първия вектор и всички числа от втория вектор, 
+като всички четни числа в новия вектор трябва да предхождат всички нечетни числа и двете групи числа (съответно четни и нечетни) трябва да са в сортиран вид всяка.
+
+***hint*** : търсим сложност Θ(size_1 + size_2), където size_1 и size_2 са големините на двата вектора.
+
+Пример:
+
+Вход:
+```
+v1 = {4, 2, 1, 3, 5, 6, 1}
+v2 = {9, 2, 3, 1, 2, 1, 2, 1}
+```
+
+Изход:
+```
+result = {2, 2, 2, 2, 4, 6, 1, 1, 1, 1, 1, 3, 3, 5, 9}
+```
+
+## Задача 3
+Даден е вектор от вектори, които са предварително сортирани. Напишете програма която merge-ва всичките 'подвектори' в един голям вектор, който също е в сортиран вид. 
+
+Тук **НЕ** ви трябва `std::sort`.
+
+***hint*** : търсим сложност Θ(size_1 + size_2 + ... + size_n), където size_i е размера на i-тия подвектор.
+
+Пример:
+
+Вход:
+```
+v = {{9, 10, 12}, {14, 17, 18}, {10, 11, 12, 22, 90}, {13}, {16, 18}}
+```
+
+Изход:
+```
+result = {9, 10, 10, 11, 12, 12, 13, 14, 16, 17, 18, 18, 22, 90}
+```
+
+## Задача 4:
+Даден е вектор от цели положителни числа. Напишете програма, която разделя масива на две части, 
+като първата част съдържа всички числа с четен брой цифри, а втората част - всички с нечетен брой. 
+
+***hint*** : търсим сложност Θ(n), където n е големината на масива.
+
+Пример:
+
+Вход:
+```
+v = {10, 2, 12, 12, 4, 100, 102020}
+```
+
+Изход:
+```
+result = {10, 12, 12, 102020, 4, 100, 2}
+```
+
+## Задача 5:
+Даден е вектор от думи, съставени изцяло от малки и главни латински букви. Напишете програма, която пренарежда вектора така, че в началото да са всички думи, 
+започващи с буквата 'а' или 'A', след тях -  тези, започващи с буквата 'b' или 'B' и т.н. Алгоритъмът да работи in-place.
+
+***hint*** : търсим сложност Θ(n), където n е големината на масива.
+
+Пример:
+
+Вход:
+```
+words = {banana, apple, Alpaca, Cat, biscuit, elephant, string, house, progress, Trousers, mouse}
+```
+
+Изход:
+```
+words = {apple, Alpaca, banana, biscuit, Cat, elephant, house, mouse, progress, string, Trousers}
+```
+
+---
+> [!IMPORTANT]
+> - Задачи 1 и 2 са за работа в час.
+> - Задачи 3 - 5 са за домашно.
+> - Задачите предавате на leetcode playground, като линк към него качвате [тук](https://docs.google.com/spreadsheets/d/1KVdic02U7f97GT2LFu67t9Z4NqyFLmCj1TjyYdrcLBE/edit?gid=0#gid=0) (всяка отделна задача я закоментирате с клавишната комбинация `Ctrl` + `/`)
+---
diff --git a/Practicum/pract03/merge.cpp b/Practicum/pract03/merge.cpp
new file mode 100644
index 0000000..68dfd5b
--- /dev/null
+++ b/Practicum/pract03/merge.cpp
@@ -0,0 +1,88 @@
+#include <iostream>
+#include <vector>
+
+// V. 1
+template<class RandomIt>
+void merge(RandomIt first1, RandomIt last1,
+    RandomIt first2, RandomIt last2,
+    RandomIt buff)
+{
+    for (; first1 != last1; ++buff)
+    {
+        if (first2 == last2)
+        {
+            for (; first1 != last1; ++first1, ++buff)
+                *buff = *first1;
+            
+            return;
+        }
+
+        if (*first2 < *first1)
+        {
+            *buff = *first2;
+            ++first2;
+        }
+        else
+        {
+            *buff = *first1;
+            ++first1;
+        }
+    }
+
+    for (; first2 != last2; ++first2, ++buff)
+        *buff = *first2;
+}
+
+// V. 2
+template <class RandomIt>
+void merge(RandomIt first1, RandomIt last1,
+    RandomIt first2, RandomIt last2,
+    RandomIt buff)
+{
+    while (first1 != last1 && first2 != last2)
+    {
+        if (*first1 <= *first2)
+        {
+            *buff = *first1;
+            ++first1;
+        }
+        else
+        {
+            *buff = *first2;
+            ++first2;
+        }
+
+        ++buff;
+    }
+
+    while (first1 != last1)
+    {
+            *buff = *first1;
+            ++first1;
+            ++buff;
+    }
+
+    while (first2 != last2)
+    {
+        *buff = *first2;
+        ++first2;
+        ++buff;
+    }
+}
+
+int main()
+{
+    std::vector<int> v1;
+    for (int i = 1; i <= 5; i++)
+        v1.push_back(i);
+
+    for (int i = 3; i <= 8; i++)
+        v1.push_back(i);
+
+    std::vector<int> v(11);
+
+    merge(v1.begin(), v1.begin() + 5, v1.begin() + 5, v1.end(), v.begin());
+
+    for (int i = 0; i < 11; i++)
+        std::cout << v[i] << " ";
+}
diff --git a/Practicum/pract03/partition.cpp b/Practicum/pract03/partition.cpp
new file mode 100644
index 0000000..dd69876
--- /dev/null
+++ b/Practicum/pract03/partition.cpp
@@ -0,0 +1,42 @@
+#include <iostream>
+#include <vector>
+
+bool isEven(int n) {
+    return !(n % 2);
+}
+
+template <class RandomIt, class Predicate>
+RandomIt partition(RandomIt first, RandomIt last, Predicate p)
+{
+    RandomIt beg = first;
+    for (; beg != last; ++beg)
+    {
+        if (!p(*beg))
+            break;
+    }
+    if (beg == last)
+        return beg;
+
+    for (RandomIt it = std::next(beg); it != last; ++it)
+    {
+        if (p(*it))
+        {
+            std::swap(*it, *beg);
+            ++beg;
+        }
+    }
+
+    return beg;
+}
+
+int main()
+{
+    std::vector<int> v;
+    for (int i = 1; i <= 10; i++)
+        v.push_back(i);
+
+    partition(v.begin(), v.end(), isEven);
+
+    for (int i = 0; i < 10; i++)
+        std::cout << v[i] << " ";
+}