From bc43abe9ce6ba84d6674b2ffad21ab60bfe0c370 Mon Sep 17 00:00:00 2001
From: Desislava Shunina <115353472+desiish@users.noreply.github.com>
Date: Tue, 15 Oct 2024 17:20:02 +0300
Subject: add pract02

---
 Practicum/pract02/readme.md | 62 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)
 create mode 100644 Practicum/pract02/readme.md

(limited to 'Practicum/pract02')

diff --git a/Practicum/pract02/readme.md b/Practicum/pract02/readme.md
new file mode 100644
index 0000000..f071435
--- /dev/null
+++ b/Practicum/pract02/readme.md
@@ -0,0 +1,62 @@
+# Практикум №2 по СД, спец. ИС
+
+## Counting Sort
+
+![1_lmzbRxK0FNgxzu8owsm4cA](https://github.com/user-attachments/assets/e679a298-8110-4fca-b375-5f52ec70f87a)
+
+[**Counting Sort**]() е ефективен алгоритъм за сортиране, подходящ за елементи с ограничен диапазон на стойности. Работи чрез преброяване на броя на срещанията на елементите. 
+
+> [!CAUTION]
+> Той не използва директно сравнения между елементите.
+
+## Сложност на Counting Sort 
+
+Counting Sort има еднаква сложност във всички случаи: най-добър случай (**best case**), най-лош случай (**worst case**) и среден случай (**average case**). Това е така, защото алгоритъмът изпълнява едни и същи операции независимо от подредбата на елементите.
+
+Нека масивът ни има **n** елемента и **k** е разликата между максималния и минималния елемент.
+
+### 1. Най-добър случай (Best Case)
+
+Най-добрият случай е, когато входните данни вече са сортирани. Въпреки това, **Counting Sort** няма оптимизация за сортирани масиви и изпълнява еднакви операции за всеки вход.
+
+> [!NOTE]
+> **Времева сложност:**
+Θ(n + k)
+
+Причината е, че:
+- Винаги се създава масив за броене с размер **k**.
+- Винаги се обхождат всички **n** елемента, за да се преброят стойностите им и след това да се копират обратно.
+
+### 2. Най-лош случай (Worst Case)
+
+Най-лошият случай е, когато елементите са напълно разбъркани. Въпреки това, **Counting Sort** изпълнява същите операции за всички входни масиви, независимо от тяхното разпределение.
+
+> [!NOTE]
+> **Времева сложност:**
+Θ(n + k)
+
+Сложността остава същата, тъй като:
+- Преброяваме всички **n** елементи в масива.
+- Инициализираме и запълваме масив с размер **k** за броене на честотите на стойностите.
+
+### 3. Среден случай (Average Case)
+
+Средният случай се случва при произволно разпределение на елементите. И тук, **Counting Sort** не е зависим от разпределението на елементите.
+
+> [!NOTE]
+> **Времева сложност:**
+Θ(n + k)
+
+Както в другите два случая, времето за изпълнение е линейно зависимо от броя на елементите **n** и диапазона на стойностите **k**.
+
+
+---
+> [!IMPORTANT]
+> Обяснение на сложността Θ(n + k)
+> - **Θ(n)**: Обхождане на входния масив с **n** елемента, за да се преброят стойностите.
+> - **Θ(k)**: Инициализация и обработка на масива за броене с **k** възможни стойности (диапазонът на елементите).
+> - **Θ(n)**: Второто обхождане на входния масив за поставяне на елементите в сортиран вид.
+
+
+---
+- [**Линк към задачите**](https://leetcode.com/problem-list/awdeugtv/)
-- 
cgit v1.3.1-23-gd82d