diff options
Add sem03 readme
1 files changed, 27 insertions, 0 deletions
| -rw-r--r-- | Seminar03/README.md | 27 |
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 |
