[courses/sdp] Added initial structure, some information about bubble and quick sorts and a resume table

1 files changed, 207 insertions, 0 deletions

diff --git a/src/courses/sdp/sorting.md b/src/courses/sdp/sorting.md
new file mode 100644
index 0000000..421ba69
--- /dev/null
+++ b/src/courses/sdp/sorting.md
@@ -0,0 +1,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|Да|&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))|
+
+## Допълнителна литература
+
+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]: Може за всяка итерация да продължим до края на поредицата с елементи, алгоритъма пак ще работи, просто няма да правим размени. По-ефикасно е ако избегнем тези излишни проверки.