[courses/sdp] Added contents and added all Други sections courses/sdp

1 files changed, 59 insertions, 8 deletions

diff --git a/src/courses/sdp/sorting.md b/src/courses/sdp/sorting.md
index 421ba69..8c069e2 100644
--- a/src/courses/sdp/sorting.md
+++ b/src/courses/sdp/sorting.md
@@ -4,6 +4,32 @@
 Всеки си има своите предимства и недостатъци, и всеки е много добър за определени ситуации и много лош за други.
 Няма всеобщ "най-добър" алгоритъм.
 
+## Съдържание
+
+1. [Характеристики]()
+   1. [Стабилност]()
+   2. [Сложност]()
+2. [Сортиране чрез вмъкване / Sorting by insertion]()
+   1. [Директно вмъкване / Insertion sort]()
+   2. [Други]()
+3. [Сортиране чрез размяна / Sorting by exchange]()
+   1. [Метод на мехурчето / Bubble sort]()
+      + [Имплементация]()
+      + [Характеристики]()
+   2. [Бързо сортиране / Quick sort]()
+      + [Имплементация]()
+      + [Характеристики]()
+4. [Сортиране чрез селекция / Sorting by selection]()
+   1. [Пряка селекция / Selection sort]()
+   2. [Други]()
+5. [Сортиране чрез сливане / Sorting by merging]()
+   2. [Други]()
+6. [Сортиране без сравнения]()
+   1. [Сортиране чрез броене / Counting sort]()
+   2. [Други]()
+7. [Обобщение]()
+8. [Допълнителна литература]()
+
 ## Характеристики
 
 ### Стабилност
@@ -12,7 +38,9 @@
 
 <br>
 
-Можем да категоризираме Сортиращите алгоритми в следните "групи"[^knuth-families]:
+Като цяло, алгоритмите за сортиране могат да се категоризират в две групи: със сравнение и без сравнение.
+Главно ще разгледаме от първия тип, обаче ще покажем и един от втория.
+Този първи тип можем допълнително да разграничим в следните "групи"[^knuth-families]:
 
 ## Сортиране чрез вмъкване / Sorting by insertion
 
@@ -63,7 +91,6 @@ void bubbleSort(int arr[], size_t n)
 }
 ```
 
-<details><summary>
 Оптимизация: Ако не разменим нито един елемент цяла итерация, значи поредицата е вече подредена
 
 ```
@@ -157,12 +184,9 @@ void quickSort(int arr[], size_t size)
 
 ##### *Бележка*
 
-Кодът, написан по точно този начин, е една доста стандартна имплементация която се среща на много места, въпреки това може да се напише доста различно.
+Има някои сравнително дребни неща които могат да се променят в тази имплементация.
 Може pivot да бъде индекс вместо стойността, може циклите за i и j да включват pivot (което ще елиминира проверката за равенство), може и финалната проверка да се намира в условието на главния цикъл (с достатъчно други изменения разбира се).
-
-Доколкото разбирам, като цяло, тези промени спокойно могат да се направят (освен може би първото предложение, понеже може да промени стабилността).
-Оригиналата статия е изязла през 1961, десетилетие преди създаването на C, така че предполагам много от тези дребни избори са останки от ранните асмебларни имплементации.
-Аргумент към тази идея е, че pivot не е индекс, а е директно стойността, (би трябвало) в асмебларни езици директно сравнение със стойност в позната памет (променлива; регистър) да е по-бързо отколкото нейното "намиране" с индекс.
+Тези промени спокойно могат да се направят, просто този вариант е най-лесен за разбиране.
 
 #### Характеристики
 
@@ -176,18 +200,45 @@ void quickSort(int arr[], size_t size)
 
 ### Пряка селекция / Selection sort
 
+### Други
+
+Основният друг такъв алгоритъм е:
+
+Пирамидално сортиране / Heap sort
+: Избираме най-големия елемент и го слагаме в сортираната част на поредицата. Разликата с пряката селекция, е че използваме heap (по-точно, за да не хабим памет, подреждаме несортираните така че да изпълняват "heap свойството") за пазене на несортираната част и така намира много по-бързо най-голямата стойност.
+
 ## Сортиране чрез сливане / Sorting by merging
 
+### / Merge sort
+
+### Други
+
+Като цяло, други видове са различните ["k-way merge"](https://en.wikipedia.org/wiki/K-way_merge_algorithm) алгоритми, които вземат k на брой сортирани поредици и ги сливат в една сортирана.
+
+## Сортиране без сравнения
+
+### Сортиране чрез броене / Counting sort
+
+### Други
+
+Любителите може да се зачетат в:
+
+Bucket sort
+: Разделя елементите в "кофи" и всяка кофа се подава пак на Bucket sort (или на друг алгоритъм, но тогава може да не е без броене), където всяка кофа съдържа конкретен диапазон от стойности, така че накрая да може всички кофи да се конкатенират. Пример е сортиране на числа, където всяка кофа ще съдържа всеки 10 числа от числовата ос (от най-малкото до най-голямото в елементите). Не е сравнение, понеже може да изберем кофата с изчисление върху стойността.
+
+Radix sort
+: Аналогичен на Bucket sort, обаче кофите съдържат определени [radix](https://en.wikipedia.org/wiki/Radix) стойности, отколкото нещо друго.
+
 ## Обобщение
 
 |Име|Стабилен|Памет|Сложност (най-лоша)|Сложност (средна)|Сложност (най-добра)|
 |---|----------|-----|--------|---|---|
-|Counting sort|Да|&Omicron;(n+k)|&Omicron;(n+k) | &Omicron;(n+k) | &Omicron;(n+k)|
 |Insertion sort|Да|&Omicron;(1)|&Omicron;(n^2 ) | &Omicron;(n^2 ) | &Omicron;(n)|
 |Bubble sort|Да|&Omicron;(1)|&Omicron;(n^2 ) | &Omicron;(n^2 ) | &Omicron;(n)|
 |Quicksort|Не|&Omicron;(1)|&Omicron;(n^2 ) | &Omicron;(n log(n)) | &Omicron;(n log(n))|
 |Selection sort|Не|&Omicron;(1)|&Omicron;(n^2 ) | &Omicron;(n^2 ) | &Omicron;(n^2 )|
 |Merge sort|Да|&Omicron;(n)|&Omicron;(n log(n)) | &Omicron;(n log(n)) | &Omicron;(n log(n))|
+|Counting sort|Да|&Omicron;(n+k)|&Omicron;(n+k) | &Omicron;(n+k) | &Omicron;(n+k)|
 
 ## Допълнителна литература