Практикум №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 = {1, 1, 2, 3, 4, 5, 6} 
v2 = {1, 1, 1, 2, 2, 2, 3, 9} 

Изход:

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, като линк към него качвате тук (всяка отделна задача я закоментирате с клавишната комбинация Ctrl + /)