From dd9a7bf0fdcc3a04fcfb18ba1613d91b46ef0833 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 20 Oct 2024 07:47:14 -0400 Subject: Add Sem02 --- README.md | 5 +- Seminar01/README.md | 45 +++++++- .../src/searching-algorithms/binary-search.cpp | 16 ++- Seminar02/README.md | 119 +++++++++++++++++++++ Seminar02/media/merge-func.png | Bin 0 -> 38442 bytes Seminar02/media/merge.png | Bin 0 -> 72511 bytes Seminar02/media/rec_tree.png | Bin 0 -> 31052 bytes Seminar02/media/recurr2.png | Bin 0 -> 78186 bytes .../src/sorting-algorithms/merge-sort-dummy.cpp | 54 ++++++++++ Seminar02/src/sorting-algorithms/merge-sort.cpp | 87 +++++++++++++++ Seminar02/src/sorting-algorithms/quick-sort.cpp | 65 +++++++++++ 11 files changed, 388 insertions(+), 3 deletions(-) create mode 100644 Seminar02/README.md create mode 100644 Seminar02/media/merge-func.png create mode 100644 Seminar02/media/merge.png create mode 100644 Seminar02/media/rec_tree.png create mode 100644 Seminar02/media/recurr2.png create mode 100644 Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp create mode 100644 Seminar02/src/sorting-algorithms/merge-sort.cpp create mode 100644 Seminar02/src/sorting-algorithms/quick-sort.cpp diff --git a/README.md b/README.md index 937d47a..e9ca9b0 100644 --- a/README.md +++ b/README.md @@ -1,4 +1,7 @@ # Код от семинаритe по структури от данни 2024/2025 - Информационни системи ## Тема 1 -Сложност на алгоритми. Сложност по време и сложност по памет. Анализ на итеративни алгоритми и примери. Алгоритми за сортиране (bubble sort, insertion sort, selection sort) и алгоритми за търсене (linear search, binary search). \ No newline at end of file +Сложност на алгоритми. Сложност по време и сложност по памет. Анализ на итеративни алгоритми и примери. Алгоритми за сортиране (bubble sort, insertion sort, selection sort) и алгоритми за търсене (linear search, binary search). + +## Тема 2 +Анализ на рекурсивни алгоритми. Quick sort и merge sort. Структури от данни. Динамичен масив (vector) използващ итератори. Амортизирана сложност и амортизиран анализ на операцията по добавяне в динамичен масив. \ No newline at end of file diff --git a/Seminar01/README.md b/Seminar01/README.md index e0fd932..31453f0 100644 --- a/Seminar01/README.md +++ b/Seminar01/README.md @@ -219,4 +219,47 @@ unsigned log_down(unsigned n, unsigned base = 2) Алгоритъм, който генерира всички подмножества на множество с големина n, би имал сложност Θ(2^n). -## Сортиращи алгоритми - bubble sort. Анализ на сложността на bubble sort. \ No newline at end of file +## Сортиращи алгоритми. Свойства на сортиращите алгоритми. + +1. Стабилност - Запазва се относителната наредба на елементите с еднакви ключове. + * Не винаги сортираме числа. При сортиране на записи (примерно информация за студенти) сортираме по ключ (примерно факултетен номер). + * Ако получим списък от записи за оценките на студенти от някой изпит, сортирани по имена, и ги сортираме със стабилен сортиращ алгоритъм по оценки, студентите с еднакви оценки ще останат сортирани и по имена. + * Ако ги сортираме с нестабилен сортиращ алгоритъм това не е сигурно. + +2. Адаптивност - Сортиращ алгоритъм нарицаме "адаптивен" ако се взема предвид текущата наредба на елементите. +3. in-place - Алгоритъм наричаме `in-place` ако не се използва допълнителна памет за неговата работа. + +## Bubble sort +* Best case: Θ(n) +* Average case: Θ(n^2) +* Worst case: Θ(n^2) + +* Стабилен сортиращ алгоритъм заради строгото неравенство. +* Адаптивен - Зависи от това какво разбираме под `почти сортиран` масив. + * [1, 2, 3, 4, 5, 4] - Bubble sort би се справил добре върху този вход. + * [2, 3, 4, 5, 1] - В случая отново ще имаме Θ(n^2) стъпки. +* in-place: да + +## Selection sort +* Best case: Θ(n^2) +* Average case: Θ(n^2) +* Worst case: Θ(n^2) + +* Нестабилен сортиращ алгоритъм. +* Адаптивен - не +* in-place - да + + +## Insertion sort +* Best case: Θ(n) +* Average case: Θ(n^2) +* Worst case: Θ(n^2) + +* Стабилен сортиращ алгоритъм. +* Адаптивен - да +* in-place - да + +## Binary search +* Best case: Θ(1) +* Average case: Θ(log(n)) +* Worst case: Θ(log(n)) \ No newline at end of file diff --git a/Seminar01/src/searching-algorithms/binary-search.cpp b/Seminar01/src/searching-algorithms/binary-search.cpp index b5befb0..7404e0a 100644 --- a/Seminar01/src/searching-algorithms/binary-search.cpp +++ b/Seminar01/src/searching-algorithms/binary-search.cpp @@ -27,7 +27,21 @@ int binarySearch(const T* arr, size_t size, T elem) return -1; } +constexpr unsigned EXAMPLE_SIZE = 7; + int main() { - + int example[EXAMPLE_SIZE] = { 1, 2, 4, 8, 16, 32, 64 }; + int needle = 4; + + int index = binarySearch(example, EXAMPLE_SIZE, needle); + if(index == -1) + { + std::cout << "Unable to find the element" << std::endl; + } + else + { + std::cout << "Element " << needle << " found at " + << index << " position: " << example[index] << std::endl; + } } \ No newline at end of file diff --git a/Seminar02/README.md b/Seminar02/README.md new file mode 100644 index 0000000..1ffcc53 --- /dev/null +++ b/Seminar02/README.md @@ -0,0 +1,119 @@ +# Втори семинар по структури от данни - 17.10.2024 + +## Анализ на рекурсивни алгоритми. +В първи семинар разгледахме метод за анализиране на итеративни алгоритми. Този метод не работи когато анализираме рекурсивни алгоритми. За да намерим сложността на рекурсивен алгоритъм използваме рекурентни уравнения. + +### Рекурентно уравнение +* Рекурентно уравнение е уравнение, което изразява общия член на някаква редица от числа чрез предишните членове. + +Рекурентните уравнения описват рекурсивни алгоритми. Разбира се, както рекурсивните алгоритми имат дъно, така и рекурентните уравнения имат начални условия. + +Нека разгледаме следния пример: +```cpp +void sum_rec(int* arr, unsigned size, int& sum) +{ + if(size == 0) + return; + + sum += arr[0]; + + return sum_rec(arr + 1, size - 1, sum); +} +``` + +Какво би било рекурентното уравнение, което описва този рекурсивен алгоритъм? Нека с променливата `n` означаваме големината на масива. + +* Разглеждаме дъното. При n = 0 имаме Θ(1) работа. +* В противен случай, имаме едно добавяне и извикване на алгоритъма с вход `n - 1`. + +Съставяме уравнението: +* T(0) = 1 +* T(n) = T(n - 1) + 1 + +Решение на рекурентно уравнение наричаме затворена формула. Решение на горния пример би било: +$$ +T(n) = n + 1 +$$ + +## Методи за решаване на рекурентни уравнения + +### 1. Чрез развиване +Винаги можем да започнем да развиваме рекурентното уравнение търсейки някаква закономерност. +$$ +T(n) = T(n - 1) + \theta(1) = T(n - 2) + \theta(1) + \theta(1) = \newline +T(0) + \theta(1) + \dots + \theta(1) = \newline +(n + 1) * \theta(1) = \theta(n) +$$ + +### Чрез дърво на рекурсията +Всеки рекурсивен алгоритъм образува дърво на рекурсията. Разглеждайки броя върхове и работата, която се "извършва" във всеки връх, височината на дървото и т.н. можем да направим изводи за решението на рекурентната редица. + +Нека разгледаме следното рекурентно уравнение: +* T(0) = 1 +* T(1) = 1 +* T(n) = 2 * T(n / 2) + n + +Това рекурентно уравнение описва работата на алгоритъмът `Merge Sort`, който ще разгледаме съвсем скоро. Как изглежда дървото на рекурсията? + +![tree-merge](media/rec_tree.png) + +Височината на това дърво е приблизително log(n). При стойност на параметъра `k = log_2(n)` стойността в листото е 1. +На всяко ниво имаме Θ(n) работа. Трябва да забележим, че работата за ниво j се смята по следната формула: +$$ +2^j * \frac{\theta(n)}{2^j} = \theta(n) +$$ + +Това ще рече броят на върховете на всяко ниво умножен по работата, която се извършва във върха на дървото. + +Щом броя на нивата е Θ(log(n)) а на всяко ниво се извършва Θ(n) работа, то търсената сложност е Θ(n log(n)). + +### Други методи + +## Примери +Нека разгледаме някои примери за рекурентни уравнения. +$$ +T(0) = \theta(1) +\newline +T(n) = 3T(n - 1) + \theta(1) +$$ + +Дървото на рекурсията би изглеждало по следния начин: +![tree-recur](media/recurr2.png) + +Нивата на това дърво ще са n на брой. Всеки елемент е с единица по - малък от баща си. Също така, на всяко ниво има 3^j върха, където j е номерът на нивото (номерираме от 0). Всеки възел извършва Θ(1) работа. Сумираме по нива: +$$ +\sum_{i = 0}^n 3^i * \theta(1) = \frac{3^{n + 1} - 1}{2} * \theta(1) = \theta(3^n) +$$ + +## Алгоритмична схема "разделяй и владей" +* Разделяй - Ако входът е достатъчно голям той се разделя на части и се преминава към стъпката **владей**. В противен случай (ако входът е достатъчно малък) задачата се решава по някакъв тривиален начин. (пример е дъното на рекурсията в `Merge Sort` където масив с големина 0 или 1 е тривиално сортиран.) +* Владей - Пускаме алгоритъма върху всяка от частите и получаваме резултатите. +* Комбинирай - Използваме тези резултати за да получим желания от нас резултат. + +## Алгоритъмът Merge Sort +Първо, нека се запознаем с функцията `merge`. Тя приема два сортирани масива и като резултат създава сортиран масив. Важно условие е масивите да са сортирани. Ако това не е така функцията не прави нищо логично. + +Ако имаме масив с n елемента и успешно сортираме лявата и дясната половина, то извиквайки функцията `merge` ще получим желания сортиран масив. Но как да сортираме лявата и дясната половина? + +Спомняме си, че пишем сортиращ алгоритъм. Извиквам mergeSort рекурсивно върху лявата и дясната половина на масива и след като ги сортира викаме функцията merge. mergeSort ще продължи да разбива масива на две, после левия и десния подмасив на още две и т.н. + +Масив от един елемент е сортиран и ще използваме този случай като дъно на рекурсията. + +Нека разгледаме следната диаграма: +![merge](media/merge.png) + +Оцветените в зелено клетки са подмасивите, на които вече е бил извикан merge. + +Следната диаграма представя визуално как работи функцията `merge`: +![merge-func](media/merge-func.png) + +Двата масива са сортирани, та има смисъл да гледаме единствено най - левите елементи. На всяка стъпка избираме по - малкия и го слагаме в резултатен масив. Трябва, разбира се, да се разгледа и случая в който масивите не са с равни дължини. + +Сложността на `Merge Sort` се описва чрез рекурентната редица, използвана като пример за решение използващо метода с дърво на рекурсията. И в трита случая имаме Θ(n log(n)) + +Стабилен - Да +Адаптивен - Не +in-place - Не +Сложност по памет - Θ(n) + +## Алгоритъмът Quick Sort \ No newline at end of file diff --git a/Seminar02/media/merge-func.png b/Seminar02/media/merge-func.png new file mode 100644 index 0000000..61db955 Binary files /dev/null and b/Seminar02/media/merge-func.png differ diff --git a/Seminar02/media/merge.png b/Seminar02/media/merge.png new file mode 100644 index 0000000..08fbfa0 Binary files /dev/null and b/Seminar02/media/merge.png differ diff --git a/Seminar02/media/rec_tree.png b/Seminar02/media/rec_tree.png new file mode 100644 index 0000000..37c39cd Binary files /dev/null and b/Seminar02/media/rec_tree.png differ diff --git a/Seminar02/media/recurr2.png b/Seminar02/media/recurr2.png new file mode 100644 index 0000000..5ea9a0f Binary files /dev/null and b/Seminar02/media/recurr2.png differ diff --git a/Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp b/Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp new file mode 100644 index 0000000..b5b2b1c --- /dev/null +++ b/Seminar02/src/sorting-algorithms/merge-sort-dummy.cpp @@ -0,0 +1,54 @@ +#include + +template +void merge(T* arr1, unsigned len1, + T* arr2, unsigned len2) +{ + T* resultArray = new T[len1 + len2]; + + unsigned cursor1 = 0; + unsigned cursor2 = 0; + unsigned resultCursor = 0; + + while (cursor1 < len1 && cursor2 < len2) + { + if (arr1[cursor1] <= arr2[cursor2]) + resultArray[resultCursor++] = arr1[cursor1++]; + else + resultArray[resultCursor++] = arr2[cursor2++]; + } + + while (cursor1 < len1) + resultArray[resultCursor++] = arr1[cursor1++]; + + while (cursor2 < len2) + resultArray[resultCursor++] = arr2[cursor2++]; + + for (size_t i = 0; i < len1 + len2; i++) + arr1[i] = resultArray[i]; + + delete[] resultArray; +} + +template +void mergeSort(T* arr, unsigned len) +{ + if (len < 2) + return; + + unsigned mid = len / 2; + + mergeSort(arr, mid); + mergeSort(arr + mid, len - mid); + + merge(arr, mid, arr + mid, len - mid); +} + +int main() +{ + int arr[4] = { 9, 6, 5, 8 }; + mergeSort(arr, 4); + + for (int i = 0; i < 4; i++) + std::cout << arr[i] << " "; +} \ No newline at end of file diff --git a/Seminar02/src/sorting-algorithms/merge-sort.cpp b/Seminar02/src/sorting-algorithms/merge-sort.cpp new file mode 100644 index 0000000..3ae3c09 --- /dev/null +++ b/Seminar02/src/sorting-algorithms/merge-sort.cpp @@ -0,0 +1,87 @@ +#include +#include +#include + +template +void merge(T* firstArray, unsigned firstSize, + T* secondArray, unsigned secondSize, + T* buffer) +{ + unsigned firstIter = 0; + unsigned secondIter = 0; + unsigned resultIter = 0; + + while(firstIter < firstSize && secondIter < secondSize) + { + if(firstArray[firstIter] > secondArray[secondIter]) + { + buffer[resultIter] = secondArray[secondIter]; + secondIter++; + } + else + { + buffer[resultIter] = firstArray[firstIter]; + firstIter++; + } + resultIter++; + } + + while(firstIter < firstSize) + { + buffer[resultIter++] = firstArray[firstIter++]; + } + + while(secondIter < secondSize) + { + buffer[resultIter++] = secondArray[secondIter++]; + } + + for (size_t i = 0; i < firstSize + secondSize; i++) + { + firstArray[i] = buffer[i]; + } +} + + +template +void mergeSortStep(T* arr, unsigned size, T* buffer) +{ + if(size < 2) + return; + + unsigned mid = size / 2; + mergeSortStep(arr, mid, buffer); + mergeSortStep(arr + mid, size - mid, buffer); + + merge(arr, mid, arr + mid, size - mid, buffer); + + for (size_t i = 0; i < size; i++) + arr[i] = buffer[i]; +} + +template +void mergeSort(T* arr, unsigned size) +{ + if(size < 2) + return; + + T* buffer = new T[size]; + mergeSortStep(arr, size, buffer); + delete[] buffer; +} + +int main() +{ + std::vector numbers; + unsigned size = rand() % 10000; + numbers.resize(size); + + for (size_t i = 0; i < size; i++) + { + numbers[i] = rand() % 10000; + } + + mergeSort(numbers.data(), numbers.size()); + + std::cout << std::is_sorted(numbers.begin(), numbers.end()) << std::endl; +} \ No newline at end of file diff --git a/Seminar02/src/sorting-algorithms/quick-sort.cpp b/Seminar02/src/sorting-algorithms/quick-sort.cpp new file mode 100644 index 0000000..3069738 --- /dev/null +++ b/Seminar02/src/sorting-algorithms/quick-sort.cpp @@ -0,0 +1,65 @@ +#include +#include // std::is_sorted +#include // std::vector + +/// @brief Reorders the elements in such a way that all elements for which are less than pivot +// precede all elements which are greater or equal to pivot. Relative order of the elements is not preserved. +// TODO: remove copy somehow??? +template +size_t partition(T* pArr, size_t len) +{ + if (pArr[0] > pArr[len - 1]) + std::swap(pArr[0], pArr[len - 1]); + + T& partitioningElement = pArr[len - 1]; + size_t left = 0; + size_t right = len - 1; + + while (true) + { + while (pArr[++left] < partitioningElement) + ; + + while (pArr[--right] > partitioningElement) + { + if (left == right) + break; + } + + if (left >= right) + break; + + std::swap(pArr[left], pArr[right]); + } + + std::swap(pArr[left], partitioningElement); + return left; +} + +template +void quickSort(T* arr, unsigned size) +{ + if(size < 2) + return; + + unsigned pivotPos = partition(arr, size); + + quickSort(arr, pivotPos); + quickSort(arr + pivotPos + 1, size - pivotPos - 1); +} + +int main() +{ + std::vector numbers; + unsigned size = rand() % 10000; + numbers.resize(size); + + for (size_t i = 0; i < size; i++) + { + numbers[i] = rand() % 10000; + } + + quickSort(numbers.data(), numbers.size()); + + std::cout << std::is_sorted(numbers.begin(), numbers.end()); +} \ No newline at end of file -- cgit v1.3.1-23-gd82d