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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
# Сортиране
Защо имаме много алгоритми за сортиране?
Всеки си има своите предимства и недостатъци, и всеки е много добър за определени ситуации и много лош за други.
Няма всеобщ "най-добър" алгоритъм.
## Характеристики
### Стабилност
### Сложност
<br>
Можем да категоризираме Сортиращите алгоритми в следните "групи"[^knuth-families]:
## Сортиране чрез вмъкване / Sorting by insertion
Такъв тип сортирания се категоризират с идеята, че всички елементи освен сегашния са сортирани и просто трябва да преместим сегашния на правилното му място.
Интуитивно е аналогично на реденето на ръка с карти: всички карти до момента са подредени, теглиш нова карта, оглеждаш се къде да я сложиш, така че всички карти пак да са подредени и я пъхаш там.
### Директно вмъкване / Insertion sort
### Други
Тези само ще споменем, не е нужно да се знаят:
Бинарно вмъкване / Binary Insertion sort
: Подобно на директното вмъкване, но правим двоично търсене, не линейно
Метод на Шел / Shellsort
: Обобщение на директното вмъкване, където правим размени първо на отдалечени елементи и постепенно намаляваме "далечината" на размени.
## Сортиране чрез размяна / Sorting by exchange
Разглеждаме само двойки елементи и ги разменяме ако не са подредени.
Груба интуиция дава физкултурният салон: когато учителят каже всички ученици да се подредят от най-висок към най-нисък, често ако подредбата не е изпълнена ученици поглеждат тези до себе си и се разменят.
### Метод на мехурчето / Bubble sort
Итерираме през всички елементи, като разменяме всеки два съседни елемента, ако първият е по-голям от вторият.
Ефектът на това е, че придвижваме по-големите елементи в края, и за една итерация през всички стойности, най-големият елемент "изплува"[^bubbling] в края.
Итерирайки през всички елементи пак, без последния[^bubblesort-limitlength], ефективно премества втория най-голям елемент в края (преди най-големия).
Продължавайки така, докато не стигнем до разглеждане на само един елемент, поредицата става подредена.
#### Имплементация
```
void bubbleSort(int arr[], size_t n)
{
for (size_t i = 0; i < n-1; i++) // "< n-1" защото винаги сравняваме с елемента в дясно на arr[i]
{
for (size_t j = 0; j < n-1-i; j++)
{
if (arr[j] > arr[j+1])
{ // може да се изведе в swap функция
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
```
<details><summary>
Оптимизация: Ако не разменим нито един елемент цяла итерация, значи поредицата е вече подредена
```
void bubbleSort(int arr[], size_t n)
{
for (size_t i = 0; i < n-1; i++)
{
bool swapped = false;
for (size_t j = 0; j < n-1-i; j++)
{
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
```
#### Характеристики
Понеже правим строги сравнения ("<" или ">"), алгоритъмът е стабилен.
Сложност
Главният му минус е, че е доста неефикасен и може да се аргументира че дори не е по-прост от Insertion sort.
Единственият "плюс" е, че е най-известният алгоритъм.
### Бързо сортиране / Quick sort
Идеята е, че за всеки елемент, искаме в ляво да са сложени всички по-малки от него, докато в дясно да са сложени всички по-големи.
Подредбата на елементите в ляво и дясно не е от значение.
След като го направим за един елемент, рекурсивно го пускаме за лявата и дясната част.
Очевидно самото подреждане се случва чрез размени.
#### Имплементация
Всеки сегашен елемент, около който ще подреждаме по-големите и по-малките елементи наричаме "pivot".
"Partition" се нарича фазата (функцията) в която слагаме елементите в ляво и в дясно от "pivot".
Можем да имплементираме partition по няколко начина, ние ще разгледаме [оригиналният начин на Hoare](https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme).
Любопитните могат да разгледат [метода на Lomuto](https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme)
Методиката е следната: имаме два индекса, начален и краен.
Началния първоначално е 0, крайния първоначално е последният възможен.
Местим началният напред докато не намерим число, което трябва да отиде в дясно на pivot.
След това местим крайния назад докато не намерим число, което трябва да отиде в ляво на pivot.
Тогава ги разменяме и почваме пак.
Това продължава докато не се "срещнат" (равни стойности) или се "разминат" (началния е след крайния).
```
size_t partition(int arr[], size_t size)
{
int pivot = arr[(i + j) / 2];
size_t i = 0; // Левият индекс
size_t j = size - 1; // Десният индекс
while (true)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (arr[i] == arr[j]) // Предотвратява зацикляне при повтарящи се елементи
i++;
if (i >= j)
return j;
std::swap(arr[i], arr[j]);
}
}
void quickSort(int arr[], size_t size)
{
if (size < 2)
return;
size_t pivot = partition(arr, size);
quickSort(arr, pivot);
quickSort(arr + pivot + 1, size - 1 - pivot);
}
```
##### *Бележка*
Кодът, написан по точно този начин, е една доста стандартна имплементация която се среща на много места, въпреки това може да се напише доста различно.
Може pivot да бъде индекс вместо стойността, може циклите за i и j да включват pivot (което ще елиминира проверката за равенство), може и финалната проверка да се намира в условието на главния цикъл (с достатъчно други изменения разбира се).
Доколкото разбирам, като цяло, тези промени спокойно могат да се направят (освен може би първото предложение, понеже може да промени стабилността).
Оригиналата статия е изязла през 1961, десетилетие преди създаването на C, така че предполагам много от тези дребни избори са останки от ранните асмебларни имплементации.
Аргумент към тази идея е, че pivot не е индекс, а е директно стойността, (би трябвало) в асмебларни езици директно сравнение със стойност в позната памет (променлива; регистър) да е по-бързо отколкото нейното "намиране" с индекс.
#### Характеристики
С
## Сортиране чрез селекция / Sorting by selection
Избираме най-малкия елемент и го "добавяме" в края на изходната (сортираната) поредица.
За да не хабим излишна памет, зачитаме левия края на списъка като сортирания списък и правим размени с елементи.
Тоест, първият най-малък елемент го разменяме с първият елемент, вторият най-малък го разменяме с втория елемент и так. нат.
### Пряка селекция / Selection sort
## Сортиране чрез сливане / Sorting by merging
## Обобщение
|Име|Стабилен|Памет|Сложност (най-лоша)|Сложност (средна)|Сложност (най-добра)|
|---|----------|-----|--------|---|---|
|Counting sort|Да|Ο(n+k)|Ο(n+k) | Ο(n+k) | Ο(n+k)|
|Insertion sort|Да|Ο(1)|Ο(n^2 ) | Ο(n^2 ) | Ο(n)|
|Bubble sort|Да|Ο(1)|Ο(n^2 ) | Ο(n^2 ) | Ο(n)|
|Quicksort|Не|Ο(1)|Ο(n^2 ) | Ο(n log(n)) | Ο(n log(n))|
|Selection sort|Не|Ο(1)|Ο(n^2 ) | Ο(n^2 ) | Ο(n^2 )|
|Merge sort|Да|Ο(n)|Ο(n log(n)) | Ο(n log(n)) | Ο(n log(n))|
## Допълнителна литература
Donald E. Knuth, [The Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition](https://archive.org/details/artofcomputerpro0003knut_w4z3)
: Една много важна и ценна книга от всеизвестния [Knuth](TODO) относно алогирми
Owen Astraten, [Bubble Sort: An Archaeological Algorithmic Analysis](https://users.cs.duke.edu/~ola/bubble/bubble.pdf)
: Кратка дисертация относно историята на популярността на Bubble sort
C. A. R. Hoare, [The Computer Journal, Volume 5, Issue 1, Pages 10-16: Quicksort](https://academic.oup.com/comjnl/article/5/1/10/395338?login=false)
: Оригиналната статия в която [Hoare](TODO) описва Quicksort
[^knuth-families]: Knuth така категоризира алгоритмите в гореспоменатата "The Art of Computer Programming, Volume 3". Важна бележка от тази книга е, че при това категоризиране не е винаги ясно в коя група даден алгоритъм се намира.
[^bubbling]: Перифразирайки [wikipedia](https://en.wikipedia.org/wiki/Bubble_sort#Debate_over_name), може да наричаме "метода на мехурчето" като "потъващо сортиране". Логиката е, че по-малките елементи са "по-леки" и затова изплуват нагоре като балнче въздух с вода. Еквивалентно, по-големите са "по-тежки" и потъват на дъното. <br> Конкретно в случая ползвам наименованието на Knuth, където по-тежките изплуват към правилното си място.
[^bubblesort-limitlength]: Може за всяка итерация да продължим до края на поредицата с елементи, алгоритъма пак ще работи, просто няма да правим размени. По-ефикасно е ако избегнем тези излишни проверки.
|
