1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
# Практикум №2 по СД, спец. ИС
## Counting Sort
[**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/)
|
