Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commit9b725efada4bb7ee5cac69130751fe4f24127a0b (patch)
Author
 Stoycho Kyosev <skyosev@2a01-5a8-317-bbdc-4f2b-da5-db2e-fb02.v6.vivacom.bg>
2024-10-25 18:09:16 -0400
Committer
 Stoycho Kyosev <skyosev@2a01-5a8-317-bbdc-4f2b-da5-db2e-fb02.v6.vivacom.bg>
2024-10-25 18:09:34 -0400
Filesb5047565c022f11419efc71c9dba2a782162093e
Data-structures-and-algorithms-9b725efada4bb7ee5cac69130751fe4f24127a0b.tar
Data-structures-and-algorithms-9b725efada4bb7ee5cac69130751fe4f24127a0b.tar.gz
Data-structures-and-algorithms-9b725efada4bb7ee5cac69130751fe4f24127a0b.zip
Parentfef45d748898639022dd71e4615c4e6253f2cad0 (diff)
Add sem03 readme
1 files changed, 27 insertions, 0 deletions
-rw-r--r--Seminar03/README.md27
diff --git a/Seminar03/README.md b/Seminar03/README.md
new file mode 100644
index 0000000..2816225
--- /dev/null
+++ b/Seminar03/README.md
@@ -0,0 +1,27 @@
+# Трети семинар по структури от данни - 24.10.2024
+
+## Долна граници на сортиране с преки сравнения. Алгоритъмът Counting sort.
+За пряко сравнение можем да си мислим като за отговор с "да" или "не" на въпроса "а по-голям ли е от b". Алгоритъм за сортиране с преки сравнения задава такива въпроси за да стигне до отговора. Разгледаните до момента алгоритми са алгоритми за сортиране с преки сравнения. Видяхме, че задачата сортиране може да се реши във време O(nlog(n)). Възможно ли е да се справим по - добре? Възможно ли е да намерим алгоритъм с по - ниска асимптотика от O(nlog(n)).
+
+Отговорът на този въпрос е не. Всеки алгоритъм за сортиране използващ преки сравнения има **долна граница Ω(nlogn)**. Това означава, че не можем да съставим алгоритъм за сортиране използващ преки сравнения и имащ сложност по-ниска от nlogn.
+
+Все пак съществуват и други алгоритми за сортиране, които не използват преки сравнения. Тяхното предимство е, че асимптотично работят по-бързо. Недостатъкът е, че не работят върху произволен тип елементи.
+
+Пример за такъв алгоритъм е **Counting sort**. Входът е масив от цели числа. Работейки с числа знаем, че всеки елемент в масива е от интервала `[min, ..., max]` (където min и max са съответно най - малкия и най - големия елемент в масива).
+
+Накратко, можем да обобщим работата му по следния начин:
+1. Създай два масива `count` и `copy`. `copy` е копия на входния масив. `count` е масив с размер max - min + 1 пълен с нули.
+2. Преброй колко пъти се среща всеки елемент на входния масив.
+ * След изпълнение на `стъпка 2` count[i - min] - колко пъти се среща i във входния масив.
+3. Последователно приложи count[i] += count[i - 1] за i от 1 до `count.size()`.
+ * Тази стъпка променя масива `count` по следния начин - count[i - min] отговаря на въпроса **коя е най - дясната позиция на i в сортираната последователност**. Наистина, преди `стъпка 3` в `count` има брой на елементите. Елементът на 0 позиция е ясен - ако имаме 3 единици най - дясната позиция на единицата е 3 (ако индексираме от 1, иначе 2). Ако имаме 3 единици и две двойки, най - дясната позиция на двойката е 5. Ако имаме 3 единици 2 двойки и 7 четворки най - дясната позиция на 4 е 12 и тн...
+4. След като знаем най - дясната позиция на всеки елемент за всеки елемент от `copy` **отдясно наляво**
+ * Постави елемента `copy[i]` на правилната (най - дясната) позиция във входния масив.
+ * Намали стойността на count[copy[i] - min]. - Това ни дава следващата позиция (тази вляво от дясната) за да може като го видим следващия път да го сложим на правилната позиция.
+
+Всички тези магии се правят за да може алгоритъма да е стабилен. Тръгването отдясно наляво (от n - 1 до 0) не е случайно - разполагаме с най - дясната позиция на всеки елемент. Логично е при три елемента първо да се справиш с най - десния.
+
+## Структури от данни
+TBI
+
+## Реализация на динамичен масив. \ No newline at end of file