Алгоритъм за сортиране: Разлика между версии
Изтрито е съдържание Добавено е съдържание
+ш без източници; форматиране: 12x заглавие-стил, 6x кавички, 6x тире, 3 интервала, нов ред (ползвайки Advisor) |
|||
Ред 1:
{{без източници|18:11, 12 март 2017 (UTC)}}
'''Алгоритъм за сортиране''' е [[алгоритъм]], който подрежда списък от елементи в определена последователност. Най-използваните подредби са числовите и лексикографските подредби. Ефективните алгоритми за сортиране са важни за оптимизацията на други алгоритми (например [[алгоритми за търсене]], [[алгоритми за сливане]] и др.), който изискват [[входните данни]] да са сортирани в определена последователност. Често също така е полезно за конкатенизиране (сливане) на данни и за генериране на разбираеми за човек крайни резултати. Формално казано, изходният резултат от [[алгоритъм за сортиране]] трябва да задоволява две условия:
Line 6 ⟶ 7:
От раждането на компютърните науки, алгоритмите за сортиране са били в процес на разработка и развитие. Ефективното решаване на проблеми, които са на пръв поглед прости и познати, се оказва доста по-сложна и трудоемка задача. Например [[метод на мехурчето|методът на мехурчето]] за пръв път е бил анализиран през 1956 година. Въпреки че мнозина са смятали проблема за сортиране за решен, нови по-ефективни алгоритми са продължавали да се откриват (например методът на библиотечното сортиране е бил публикуван за първи път през 2006 година). Алгоритмите за сортиране често се представят в началните класове по компютърни науки, където изобилието от алгоритми за решаването на един проблем елегантно показва разнообразието от ключови алгоритмични концепции, като например [[голямото '''О''']], [[разделяй и владей]], [[структурни данни]], [[случайни алгоритми]], [[най-добър, най-лош и среден случай]], [[компромис време-памет]], [[горна и долна граница]].
== Класификация ==
Сортиращите алгоритми често се класифицират по:
* [[Теория на изчислителната сложност|Изчислителна сложност]] при сравняване на елементите (най-лош, среден и най-добър случай) при сравняване на елементи в списък от (''n'') елемента. Добър пример за серийно сортиране O(''n'' log ''n''), за паралелно сортиране O(log<sup>2</sup> ''n''), и за лошо сортиране O(''n''<sup>2</sup>). Вижте нотацията на [[голямото '''О''']]. Идеалният резултат при серийно сортиране е
* Използвана памет (и други компютърни ресурси)
* [[Рекурсия|Рекурсивни]]. Някои алгоритми са или рекурсивни, или не-рекурсивни, докато други могат да съчетават и двата вида като например (алгоритъмът за [[сортиране чрез сливане]])
* Стабилност
* Дали са сравняващи алгоритми
* Адаптиращи се алгоритми
=== Стабилност ===
[[File:Sorting stability playing cards.svg|thumb|Пример за стабилно сортиране с карти за игра. Когато картите са сортирани по ранг чрез стабилно сортиране, двете петици би следвало да останат в началната си последователност. Когато сортирането е нестабилно, двете петици могат да разменят местата си понякога в крайния резултат.]]
Когато се сортират някакви данни, само част от техните признаци се анализират при тяхното подреждане. Примерът от дясно показва, че картите са сортирани по ранг (от 2 до 7), а техният цвят се игнорира. От това следва, че крайният резултат може да бъде различен. Алгоритмите за стабилно сортиране използват следното правило: ако два елемента при сравнение са еднакви (като например двете петици), то тяхната първоначална подредба ще бъде съхранена, така че ако едната от тях е преди другата в началната подредба, то тя ще бъде първа и в крайният резултат.
Line 30 ⟶ 31:
Размяната на ключовете може обаче да доведе до нестабилно сортиране. Отново примера с картите – ако първо се сравнява по цвят, а после по ранг, не винаги крайният резултат ще бъде един и същ.
=== Сравнение на алгоритмите ===
В таблицата, ''n'' е номерата на записи, които трябва да се сортират. Колоните
{|class="wikitable sortable"
Line 45 ⟶ 46:
25 - n^2,
30 - n^c (c > 2),
40
45
50
|- align="center"
|[[Бързо сортиране]]
Line 102 ⟶ 103:
| вмъкване
|align=left| Малък блок код, без Small code size, не използва стек на извикванията, разумно бърз, полезен, където паметта е приоритет, като например вградените и по-старите майнфрейм приложения
|- align="center"
|[[Метод на мехурчето]]
|style="background:#ddffdd"|{{Sort|15|<math>\mathcal{} n</math>}}
Line 123 ⟶ 124:
|}
== Представяне на по-популярните алгоритми за сортиране ==
=== Метод на мехурчето ===▼
▲===Метод на мехурчето===
[[File:Bubble sort animation.gif|150px|thumb| Метод на мехурчето]]
{{Основна|Метод на мехурчето}}
Ред 131:
''Методът на мехурчето'' ({{lang-en|Bubble sort}}) е прост сортиращ алгоритъм. Алгоритъмът започва в началото на сортиращия се списък. Той сравнява първия и втория елемент, и ако първият е по-голям от втория, ги разменя. Продължава да прави с това с всички съседни двойки елементи до края на сортиращия се списък. След това повтаря същото действие още толкова пъти, докато накрая при обхождането на целия списък не е направено нито една размяна на два съседни елемента. Средният и най-лош случай на този алгоритъм е O(''n''<sup>2</sup>) и не се използва за сортиране на големи неподредени множества от данни. Методът на мехурчето може да се използва за малки множества или за множества, където има елементи близо до очакваното си място. Например, ако някой елемент не е на мястото си, на разстояние един елемент (например 112 и 111), методът на мехурчето ще обходи един път множеството и ще направи размяната, а на второто обхождане няма да направи размяна и ще завърши сортирането, и това ще отнеме само 2''n''.
=== Сортиране чрез пряка селекция ===
[[File:Selection sort animation.gif|150px|thumb| Сортиране чрез пряка селекция]]
{{Основна|Сортиране чрез пряка селекция}}
Ред 138:
Алгоритъмът намира най-малкия елемент в списъка и го разменя с първия елемент. След това търси втория най-малък и го поставя на второ място. Действието се повтаря, докато се стигне до края на списъка. При този алгоритъм не се правят повече от ''n'' размени. Този алгоритъм е полезен в случаи, когато размяната на елементи е тежка операция и трябва да се минимизира.
=== Сортиране чрез вмъкване ===
{{Основна|Сортиране чрез вмъкване}}
''Сортирането чрез вмъкване'' ({{lang-en|Insertion sort}}) е прост алгоритъм, който е относително ефективен при малки и почти сортирани списъци, като често се използва в комбинация с по-усъвършенствани алгоритми. Алгоритъмът работи като взема всеки елемент един по-един от списъка и го вмъква на съответното си място в нов сортиран списък. При сортиране на масиви елементите могат да споделят базовата памет (пространство), но се извършват прекалено много премествания на елементи което е скъпа операция. Шел сортирането е по-усъвършенстваният вариант за по-големи списъци.
=== Шел сортиране ===
{{Основна|Шел сортиране}}
''Шел сортирането'' е открито от Доналд Шел през 1959 година. То подобрява метода на мехурчето и сортирането чрез вмъкване чрез преместването на елементите през повече от една позиция в даден момент. Може да бъде описано като нареждане на последователни елементи в двумерен масив и след това сортирането на колоните на масива чрез ''сортиране чрез вмъкване''
=== Сортиране чрез сливане ===
{{Основна|Сортиране чрез сливане}}
''Сортирането чрез сливане'' ({{lang-en|Merge sort}}) използва принципа на сливане на вече сортирани списъци. Започва с обединяването на всяка двойка елементи (например 1 и 2, после 3 и 4 ...) и ги разменя ако първата двойка трябва да е след втората. След това слива всички списъци от два елемента в списъци от четири, отново ги пренарежда и ги слива в списъци от осем и т.н., докато останат само два списъка, които се сливат последно за да приключи сортирането. Този алгоритъм се представя добре при списъци с големи мащаби и при най-лош случай има ефективност O(''n'' log ''n''). Също така се прилага лесно както за масиви, така и за списъци, стига да предоставя последователен достъп към елементите. Минус е обаче ефективността на памет O(''n''), както и прекалено многото използване на прости операции като присвояване и копиране.
=== Пирамидално сортиране ===
[[File:Max-Heap.svg|150px|thumb|Пример за хийп двоично дърво]]
{{Основна|Пирамидално сортиране}}
''Пирамидалното сортиране''({{lang-en|Heapsort}}) е много по-ефективно от [[Сортиране чрез пряка селекция|Сортирането чрез пряка селекция]]. Този вид сортиране на принципа на определяне на най-малкия и най-големия елемент в списъка и поставянето им в двата края, след което прави същото и за останалата част на несортирания списък. За да се реализира този алгоритъм, несортираният списък
=== Сортиране чрез броене ===
{{Основна|Сортиране чрез броене}}
Сортирането чрез броене е [[алгоритъм за сортиране]] на група от обекти спрямо техните ключове, които са малки цели числа; това е алгоритъм за сортиране на цели числа. Алгоритъмът се изпълнява, като брои обектите с различни стойности на ключа, и използвайки аритметика за тези числа за определяне на позициите на всяка ключова стойност в изходната поредица. Времето за изпълнение е линейно в рамките на броя на елементите и разликата между максималната и минималната ключова стойност, така че е подходящ само за директна употреба в случаите, когато разликата в ключовете не е значително по-голяма от броя на елементите.
Ред 161:
=== Бързо сортиране ===
{{Основна|Бързо сортиране}}
Алгоритъмът за бързо сортиране ({{lang-en|Quicksort}}) е един от най-добрите алгоритми за търсене на голям брой елементи. Нарича се още алгоритъмът на Хор, заради името на човека, който го е измислил
=== Bucket сортиране ===
{{Основна| Bucket сортиране}}
Bucket sort, или bin sort, е сортиращ алгоритъм, който работи чрез разделяне на един масив в определен брой контейнери. След това всеки
=== Сортиране по метода на гребена ===
Ред 171:
Сортирането по метода на гребена е прост алгоритъм за сортиране, първоначално разработен от Владимир Добошевич през 1980 г. По-късно алгоритъмът е преоткрит от Стефан Ласи и Ричард Бокс през 1991 г. Алгоритъмът на гребена подобрява метода на мехурчето.
== Модели за използване на паметта и сортиране чрез индекси ==
Когато размерът на сортиращия масив започне да доближава или превишава наличната основна памет и алгоритъмът започне да се изпълнява по-бавно поради причината, че започва да използва виртуалната памет намираща се на твърдия диск, моделите за организиране на паметта започват да играят по-голяма роля, а алгоритмите за сортиране които на пръв поглед работят по-бързо (когато масивите им се побират в оперативната памет) започват да се изпълняват много по-бавно. При такива сценарии броят на сравнения става относително по-маловажен, а броят четене и писане в оперативната памет и диска става по-значителен при производителността на даден алгоритъм.
Например популярният алгоритъм за сортиране [[бързо сортиране]] предлага достатъчно добра производителност при налична оперативна памет, но заради рекурсивната си природа този алгоритъм прави прекалено много копия на сортиращият се масив и когато излезе извън границите на оперативната си памет и започне да се използва твърдия диск, производителността му рязко спада.
Един начин да се заобиколи този проблем, който работи добре при по-сложните записи (като например [[Релационна база данни|релационните бази данни]]), е списъците да се сортират по относително малки по обем ключове (индекси), вместо целите записи. След това с едно обхождане могат да се сортират всички записи на базата на техните индекси, въпреки че това не е необходимо тъй като индексите сочат към съответните си записи. Такова сортиране се нарича още така
Друг подход за решаване на проблема с паметта е да се комбинират няколко сортиращи алгоритъма така, че да се използват само силните им страни.
| |||