diff options
Add Sem02
2 files changed, 59 insertions, 2 deletions
| -rw-r--r-- | Seminar01/README.md | 45 | ||||
| -rw-r--r-- | Seminar01/src/searching-algorithms/binary-search.cpp | 16 |
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 |
