Алгоритъм за сортиране: Разлика между версии

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

# Изходният резултат е пермутация (пренаредба) на входните елементи.

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

* [[Теория на изчислителната сложност|Изчислителна сложност]] при сравняване на елементите (най-лош, среден и най-добър случай) при сравняване на елементи в списък от (''n'') елемента. Добър пример за серийно сортиране O(''n'' log ''n''), за паралелно сортиране O(log² ''n''), и за лошо сортиране O(''n''²). Вижте нотацията на [[голямото '''О''']]. Идеалният резултат при серийно сортиране е O(''n''), но това не е постижимо в повечето случаи. Оптималното паралелно сортиране е O(log ''n''). Сравняващо-базираните алгоритми за сортиране, които оценяват списъкътсписъка с елементи на базата на абстрактна ключова операция за сравнение, имат нужда от поне O(''n'' log ''n'') сравнения при сортиране

* [[Рекурсия|Рекурсивни]]. НякойНякои алгоритми са или рекурсивни, или не-рекурсивни, докато други могат да съчетават и двата вида като например (алгоритъмът за [[Сортиране чрез сливане|сортиране чрез сливане]])

[[File:Sorting stability playing cards.svg|thumb|Пример за стабилно сортиране с карти за игра. Когато картите са сортирани по ранг чрез стабилно сортиране, двете петици би следвало да останат в началната си последователност. Когато сортирането е нестабилно, двете петици могат да разменят местата си понякога в крайнияткрайния резултат.]]

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

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

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

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

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

|style="background:#ffffdd"|{{Sort|05|<math>\mathcal{} \log n</math> при среден, <math>n</math> в най-лошиятлошия случай}}

|style="background:#ffdddd"|{{Sort|15|Зависи; в най-лошиятлошия случай е <math> \mathcal{} n </math>}}

|align=left| Малък блок код, без Small code size, не използва стек на извикванията, разумно бърз, полезен, където паметта е приоритет, като например вградените и по-старите майнфрейм приложения

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

АлгоритъмаАлгоритъмът за сортиране чрез пряка селекция ({{lang-en|Selection sort}}) е неефективен със изчислителна сложност O''n''². Подобен алгоритъм, който има по-добра производителност, е алгоритъмът за [[сортиране чрез вмъкване]]. Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.

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

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

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

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

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

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

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

Един начин да се заобиколи този проблем, който работи добре при по-сложните записи (като например [[Релационна база данни|релационните бази данни]]), е списъците да се сортират по относително малки по обем ключове (индекси), вместо целите записи. След това с едно обхождане могат да се сортират всички записи на базата на техните индекси, въпреки че това не е необходимо тъй като индексите сочат към съответните си записи. Такова сортиране се нарича още така "тагово сортиране".