Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar01
diff options
context:
space:
mode:
Commitdd9a7bf0fdcc3a04fcfb18ba1613d91b46ef0833 (patch)
Author
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-20 07:47:14 -0400
Committer
 Stoycho Kyosev <skyosev@192.168.100.17>
2024-10-20 07:47:14 -0400
Files0e517f48f127dc1cb5418dacc61e48959ad34eb4 /Seminar01
Data-structures-and-algorithms-dd9a7bf0fdcc3a04fcfb18ba1613d91b46ef0833.tar
Data-structures-and-algorithms-dd9a7bf0fdcc3a04fcfb18ba1613d91b46ef0833.tar.gz
Data-structures-and-algorithms-dd9a7bf0fdcc3a04fcfb18ba1613d91b46ef0833.zip
Parent8b287b482452f58491a2e1514cb37aa27b05929a (diff)
Add Sem02
2 files changed, 59 insertions, 2 deletions
-rw-r--r--Seminar01/README.md45
-rw-r--r--Seminar01/src/searching-algorithms/binary-search.cpp16
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