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

===Метод на мехурчето===

[[File:Bubble sort animation.gif|150px|thumb|right| Метод на мехурчето]]

 

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

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

[[Image:Selection sort animation.gif|150px|right|thumb| Сортиране чрез пряка селекция]]

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

 

 

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

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

 

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

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

 

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

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

 

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

[[Image:Max-Heap.svg|150px|right|thumb|Пример за хийп двоично дърво]]

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

 

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

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

 

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

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

 

=== Bucket сортиране ===

Bucket sort, или bin sort, е сортиращ алгоритъм, който работи чрез разделяне на един масив в определен брой контейнери. След това всеки "контейнер" се сортира индивидуално, или чрез използване на различни сортиращи алгоритми, или чрез рекурсивно прилагане на bucket сортиране. Bucket сортиране е обобщаващ на pigeonhole sort, алгоритъм. Пресмятането на изчислителната сложност включва броя на използваните "контейнери". Bucket sort може да се изпълнява с линейно време - (Θ(n)). Всяка кофа трябва да съдържа или един елемент, или да се сортира.

 

=== Сортиране по метода на гребена ===

Сортирането по метода на гребена е прост алгоритъм за сортиране, първоначално разработен от Владимир Добошевич през 1980 г. По-късно алгоритъмът е преоткрит от Стефан Ласи и Ричард Бокс през 1991 г. Алгоритъмът на гребена подобрява метода на мехурчето.