diff options
1 files changed, 59 insertions, 8 deletions
| -rw-r--r-- | src/courses/sdp/sorting.md | 67 |
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|Да|Ο(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))| +|Counting sort|Да|Ο(n+k)|Ο(n+k) | Ο(n+k) | Ο(n+k)| ## Допълнителна литература |