# Практикум №2 по СД, спец. ИС

## Counting Sort

![1_lmzbRxK0FNgxzu8owsm4cA](https://github.com/user-attachments/assets/e679a298-8110-4fca-b375-5f52ec70f87a)

[**Counting Sort**](https://github.com/stoychoX/Data-structures-and-algorithms/blob/main/Practicum/pract02/CountingSort.cpp) е ефективен алгоритъм за сортиране, подходящ за елементи с ограничен диапазон на стойности. Работи чрез преброяване на броя на срещанията на елементите. 

> [!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/)