Алгоритъм за сортиране е алгоритъм, който подрежда списък от елементи в определена последователност.[Наков, П., Добриков, П. Програмиране = ++Алгоритми, С., 2003, стр. 199] Най-използваните подредби са числовите и лексикографските подредби. Ефективните алгоритми за сортиране са важни за оптимизацията на други алгоритми (например алгоритми за търсене, алгоритми за сливане и др.), който изискват входните данни да са сортирани в определена последователност. Често също така е полезно за конкатенизиране (сливане) на данни и за генериране на разбираеми за човек крайни резултати. Формално казано, изходният резултат от алгоритъма за сортиране трябва да задоволява две условия:

Изходният резултат е в ненамаляваща последователност (всеки елемент не трябва да е по-малък от предходните на базата на очакваната обща подредба); Изходният резултат е пермутация (пренаредба) на входните елементи.

От раждането на компютърните науки, алгоритмите за сортиране са били в процес на разработка и развитие. Ефективното решаване на проблеми, които са на пръв поглед прости и познати, се оказва доста по-сложна и трудоемка задача. Например методът на мехурчето за пръв път е бил анализиран през 1956 година. Въпреки че мнозина са смятали проблема за сортиране за решен, нови по-ефективни алгоритми са продължавали да се откриват (например методът на библиотечното сортиране е бил публикуван за първи път през 2006 година). Алгоритмите за сортиране често се представят в началните класове по компютърни науки, където изобилието от алгоритми за решаването на един проблем елегантно показва разнообразието от ключови алгоритмични концепции, като например голямото О, разделяй и владей, структурни данни, случайни алгоритми, най-добър, най-лош и среден случай, компромис време-памет, горна и долна граница.

Класификация Сортиращите алгоритми често се класифицират по:

Изчислителна сложност при сравняване на елементите (най-лош, среден и най-добър случай) при сравняване на елементи в списък от (n) елемента. Добър пример за серийно сортиране O(n log n), за паралелно сортиране O(log2 n), и за лошо сортиране O(n2). Вижте нотацията на голямото О. Идеалният резултат при серийно сортиране е O(n), но това не е постижимо в повечето случаи. Оптималното паралелно сортиране е O(log n). Сравняващо-базираните алгоритми за сортиране, които оценяват списъка с елементи на базата на абстрактна ключова операция за сравнение, имат нужда от поне O(n log n) сравнения при сортиране Използвана памет (и други компютърни ресурси) Рекурсивни. Някои алгоритми са или рекурсивни, или не-рекурсивни, докато други могат да съчетават и двата вида като например (алгоритъмът за сортиране чрез сливане) Стабилност Дали са сравняващи алгоритми – сравняващите алгоритми сравняват два елемента с оператор за сравнение Адаптиращи се алгоритми

Стабилност

Когато се сортират някакви данни, само част от техните признаци се анализират при тяхното подреждане. Примерът от дясно показва, че картите са сортирани по ранг (от 2 до 7), а техният цвят се игнорира. От това следва, че крайният резултат може да бъде различен. Алгоритмите за стабилно сортиране използват следното правило: ако два елемента при сравнение са еднакви (като например двете петици), то тяхната първоначална подредба ще бъде съхранена, така че ако едната от тях е преди другата в началната подредба, то тя ще бъде първа и в крайния резултат.

Когато еднаквите елементи са неразличими, като целочислените числа или други по-общи данни където всеки елемент е уникален по всичките си признаци, стабилността не е проблем. Стабилността не е проблем и когато всички елементи са различни.

Нестабилното сортиране може да бъде превърнато в стабилно чрез допълнително разширяване логиката за сравняване, така че сравняването на два елемента, които по един признак са еднакви, да бъдат различени по един или повече други признаци. Това допълнително разширение обаче води до нуждата от допълнително време и памет.

Един подход за стабилно сортиращи алгоритми е сортиране на списъци по първичен и вторичен ключ. Например, при сортиране на група от карти първият ключ ще бъде техният ранг (2,3,4, …, А), а вторият техният цвят (♣,♦,♥, ♠). Това може да стане с един и същ алгоритъм за сортиране, но с различен ключ за сравняване:

Размяната на ключовете може обаче да доведе до нестабилно сортиране. Отново примера с картите – ако първо се сравнява по цвят, а после по ранг, не винаги крайният резултат ще бъде един и същ.

Сравнение на алгоритмите В таблицата, n е номерата на записи, които трябва да се сортират. Колоните „Средно“ и „Най-лошо“ показват времевата сложност (също така наречена изчислителна сложност) на всеки от алгоритмите. Колоната „Памет“ е за паметта, която се изисква, както допълнение към базовата памет (съхраняваща списъка с елементи), необходима за извършване операции и преподредба на елементите при съответния алгоритъм за сортиране. Всички по-долу са сравняващи сортиращи алгоритми и те не могат да бъдат с по-добра производителност от O(n log n) в сродения си или най-лошия си случай. Времето за изпълнение и паметта използвана от алгоритмите може да бъде измерена чрез различни нотации като например – тета, омега, голямото-О, малкото-О и други. Паметта и времето за изпълнение по-долу е приложимо за всичките видове нотации.

+ Сортиране чрез сравнениеИме Най-добър Среден Най-лош Памет Стабилен Метод БележкиБързо сортиране Зависи разделянеБързото сортиране обикновено се прави с O(log(n)) стеково пространство. Повечето му имплементации са нестабилни, като при реализиране на стабилно сортиране както сложността на алгоритъма, така и нуждата от допълнителна памет се увеличаваСортиране чрез сливане Да сливане Сортиране чрез сливане е високо паралелистичен (до O(log(n))Пирамидално сортиране Не селекция Сортиране чрез вмъкване Да вмъкванеO(n + d), където d е броят на преместваниятаСортиране чрез пряка селекция Не селективно Стабилно с O(n) допълнително пространство или с използване на допълнителни списъци.Шел сортиране Не вмъкване Малък блок код, без Small code size, не използва стек на извикванията, разумно бърз, полезен, където паметта е приоритет, като например вградените и по-старите майнфрейм приложенияМетод на мехурчето Да Размяна Кратък кодСортиране с помощта на двоично дърво Да Вмъкване Когато се използват алгоритъм за търсене в балансирано дърво

Представяне на по-популярните алгоритми за сортиране Метод на мехурчето

Методът на мехурчето () е прост сортиращ алгоритъм. Алгоритъмът започва в началото на сортиращия се списък. Той сравнява първия и втория елемент, и ако първият е по-голям от втория, ги разменя. Продължава да прави с това с всички съседни двойки елементи до края на сортиращия се списък. След това повтаря същото действие още толкова пъти, докато накрая при обхождането на целия списък не е направено нито една размяна на два съседни елемента. Средният и най-лош случай на този алгоритъм е O(n2) и не се използва за сортиране на големи неподредени множества от данни. Методът на мехурчето може да се използва за малки множества или за множества, където има елементи близо до очакваното си място. Например, ако някой елемент не е на мястото си, на разстояние един елемент (например 112 и 111), методът на мехурчето ще обходи един път множеството и ще направи размяната, а на второто обхождане няма да направи размяна и ще завърши сортирането, и това ще отнеме само 2n.

Сортиране чрез пряка селекция

Алгоритъмът за сортиране чрез пряка селекция () е неефективен с изчислителна сложност On2. Подобен алгоритъм, който има по-добра производителност, е алгоритъмът за сортиране чрез вмъкване. Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.

Алгоритъмът намира най-малкия елемент в списъка и го разменя с първия елемент. След това търси втория най-малък и го поставя на второ място. Действието се повтаря, докато се стигне до края на списъка. При този алгоритъм не се правят повече от n размени. Този алгоритъм е полезен в случаи, когато размяната на елементи е тежка операция и трябва да се минимизира.

Сортиране чрез вмъкване

Сортирането чрез вмъкване () е прост алгоритъм, който е относително ефективен при малки и почти сортирани списъци, като често се използва в комбинация с по-усъвършенствани алгоритми. Алгоритъмът работи като взема всеки елемент един по-един от списъка и го вмъква на съответното си място в нов сортиран списък. При сортиране на масиви елементите могат да споделят базовата памет (пространство), но се извършват прекалено много премествания на елементи което е скъпа операция. Шел сортирането е по-усъвършенстваният вариант за по-големи списъци.

Шел сортиране

Шел сортирането е открито от Доналд Шел през 1959 година. То подобрява метода на мехурчето и сортирането чрез вмъкване чрез преместването на елементите през повече от една позиция в даден момент. Може да бъде описано като нареждане на последователни елементи в двумерен масив и след това сортирането на колоните на масива чрез сортиране чрез вмъкване

Сортиране чрез сливане

Сортирането чрез сливане () използва принципа на сливане на вече сортирани списъци. Започва с обединяването на всяка двойка елементи (например 1 и 2, после 3 и 4 ...) и ги разменя ако първата двойка трябва да е след втората. След това слива всички списъци от два елемента в списъци от четири, отново ги пренарежда и ги слива в списъци от осем и т.н., докато останат само два списъка, които се сливат последно за да приключи сортирането. Този алгоритъм се представя добре при списъци с големи мащаби и при най-лош случай има ефективност O(n log n). Също така се прилага лесно както за масиви, така и за списъци, стига да предоставя последователен достъп към елементите. Минус е обаче ефективността на памет O(n), както и прекалено многото използване на прости операции като присвояване и копиране.

Пирамидално сортиране

Пирамидалното сортиране() е много по-ефективно от Сортирането чрез пряка селекция. Този вид сортиране на принципа на определяне на най-малкия и най-големия елемент в списъка и поставянето им в двата края, след което прави същото и за останалата част на несортирания списък. За да се реализира този алгоритъм, несортираният списък се представя като специална структура от данни heap, наречена Двоично дърво. Веднъж представен списъкът по този начин се гарантира, че коренът на дървото има най-големия (или най-малкия) елемент от списъка. Когато този елемент се вземе и постави в началото на сортирания списък, останалите елементи се пренареждат отново така че да коренът отново да бъде най-големият (или най-малкият) елемент от останалия несортиран списък. Използвайки хийпът намирането на най-големия елемент отнема O(log n) време, вместо O(n) при линейно търсене. Това позволява пирамидалното сортиране да има времева ефективност O(n log n), както и при най-лош сценарий.

Сортиране чрез броене

Сортирането чрез броене е алгоритъм за сортиране на група от обекти спрямо техните ключове, които са малки цели числа; това е алгоритъм за сортиране на цели числа. Алгоритъмът се изпълнява, като брои обектите с различни стойности на ключа, и използвайки аритметика за тези числа за определяне на позициите на всяка ключова стойност в изходната поредица. Времето за изпълнение е линейно в рамките на броя на елементите и разликата между максималната и минималната ключова стойност, така че е подходящ само за директна употреба в случаите, когато разликата в ключовете не е значително по-голяма от броя на елементите.

Бързо сортиране

Алгоритъмът за бързо сортиране () е един от най-добрите алгоритми за търсене на голям брой елементи. Нарича се още алгоритъмът на Хор, заради името на човека, който го е измислил – Тони Хор. Този алгоритъм прави O(n log n) сравнения за да сортира n на брой елемента. В практиката алгоритъмът за бързо сортиране е по-бърз от другите O(n log n) алгоритми. Неговата имплементация се извършва с рекурсия.

Bucket сортиране