# Сортиране Защо имаме много алгоритми за сортиране? Всеки си има своите предимства и недостатъци, и всеки е много добър за определени ситуации и много лош за други. Няма всеобщ "най-добър" алгоритъм. ## Съдържание 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. [Допълнителна литература]() ## Характеристики ### Стабилност ### Сложност
Като цяло, алгоритмите за сортиране могат да се категоризират в две групи: със сравнение и без сравнение. Главно ще разгледаме от първия тип, обаче ще покажем и един от втория. Този първи тип можем допълнително да разграничим в следните "групи"[^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; } } } } ``` Оптимизация: Ако не разменим нито един елемент цяла итерация, значи поредицата е вече подредена ``` 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 (което ще елиминира проверката за равенство), може и финалната проверка да се намира в условието на главния цикъл (с достатъчно други изменения разбира се). Тези промени спокойно могат да се направят, просто този вариант е най-лесен за разбиране. #### Характеристики С ## Сортиране чрез селекция / Sorting by selection Избираме най-малкия елемент и го "добавяме" в края на изходната (сортираната) поредица. За да не хабим излишна памет, зачитаме левия края на списъка като сортирания списък и правим размени с елементи. Тоест, първият най-малък елемент го разменяме с първият елемент, вторият най-малък го разменяме с втория елемент и так. нат. ### Пряка селекция / 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) стойности, отколкото нещо друго. ## Обобщение |Име|Стабилен|Памет|Сложност (най-лоша)|Сложност (средна)|Сложност (най-добра)| |---|----------|-----|--------|---|---| |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))| |Counting sort|Да|Ο(n+k)|Ο(n+k) | Ο(n+k) | Ο(n+k)| ## Допълнителна литература 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), може да наричаме "метода на мехурчето" като "потъващо сортиране". Логиката е, че по-малките елементи са "по-леки" и затова изплуват нагоре като балнче въздух с вода. Еквивалентно, по-големите са "по-тежки" и потъват на дъното.
Конкретно в случая ползвам наименованието на Knuth, където по-тежките изплуват към правилното си място. [^bubblesort-limitlength]: Може за всяка итерация да продължим до края на поредицата с елементи, алгоритъма пак ще работи, просто няма да правим размени. По-ефикасно е ако избегнем тези излишни проверки.