Алгоритам сортирања је алгоритам који ставља елементе листе у одређеном редоследу. Највише коришћена наређења су нумерички и лексичко-графички ред. Ефикасно сортирање је важно за оптимизацију коришћења других алгоритама (као што су алгоритми претраге и спајања) које захтевају унос података у сортиране листе; такође је често корисно за "канонизоване" податаке и за производњу људски разумљивих излазних вредности. Формалније речено, излаз мора задовољити два услова: Излаз је у растућем редоследу (сваки елемент је већи од претходног елемента према жељеном редоследу); Излаз је пермутација (преуређена) улаза.
Даље, подаци се радије узимају да буду низ, који омогућава насумичан приступ, него листа која дозвољава само секвенцијални приступ, мада често алгоритми се могу примењивати уз погодну модификацију за обе врсте података.
Од настанка рачунарства, проблем сортирања је привукао велика истраживања, можда због сложености његовог ефикасног решавања упркос свом једноставном обрачун. На пример, "мехурасто сортирање" је анализиран већ 1956. године.Demuth, H. Electronic Data Sorting. Основна граница сортирања поређења алгоритама је да они захтевају време извршавања – O(n log n) – у најгорем случају, мада боље перформансе је могуће извести на стварним подацима (као што су сортирани подаци), и алгоритама који нису основани на поређењу, као што је бројање врсти, могу имати боље перформансе. Иако многи сматрају сортирање као решен проблем - асимптотично оптимални алгоритми су познати још од средине 20. века – корисни нови алгоритми се још увек праве са сада већ увелико коришћеним тимсорт из 2002. године, и библиотечко сортирање које се први пут појавило 2006. године.
Алгоритми сортирања су распрострањени у уводу информатике, где обиље алгоритама за проблем пружа благи увод у разне концепте алгоритма као што су " велико О", подели па владај алгоритми, структуре података као што су гомиле и бинарна стабла, "случајни алгоритми", анализа најбољи, најгори и просечан случај, компромиси временског простора, као и горња и доња граница.
Класификација Алгоритми сортирања се често деле по: Комплексности (најгоре, просечно и најбоље понашање) поређења елемената у смислу величине листе (н). За типичне алгоритме сортирања, добро понашање је O(n log n), са паралелним сортирањем је O(log2 n), а најгоре је О(n2). (погледај "велико О") Идеално понашање за серијско сортирање је O(n), али ово није могуће у просечном случају. Најповољније за паралелно сортирање је O(log). Поређење сортирања алгоритама, које процењује елементе листе путем апстрактног кључног поређења рада захтева најмање O (n log n) поређења за већину улазних вредности. Сложеност размене (за "на месту" алгоритама). Меморијска искоришћеност (и коришћење других рачунарских ресурса). Посебно, неки алгоритми за сортирање су "на месту". "На месту" врсте захтева само О (1) меморије изван ставки које су сортиране; Понекад се O (log (n)) додатне меморије сматра "на месту". Рекурзија. Неки алгоритми су или рекурзивни или не-рекурзивни, док други могу бити оба (нпр. интегрисано сортирање). Стабилност: стабилни алгоритми за сортирање одрже релативан ред записа са једнаким кључевима (тј. вредностима). Без обзира да ли је то сортирање поређењем или не. Сортирање поређењем испитује податке само поређењем два елемента са оператором поређења. Општи метод: уметање, размена, избор, спајање, итд. Сортирање разменом се састоји из мехурастог и брзог сортирања. Селективно сортирање чине мешовито и нагомилано сортирање. Такође, ту се гледа да ли је серијско или паралелно. Остатак ове дискусије се готово искључиво концентрише на серијске алгоритме и серијски рад. Прилагодљивост: Да ли преуређеност од улаза утиче или не на време рада. Алгоритми који се узимају у обзир су адаптивни.
Стабилност мини|Пример стабилног сортирање на картама. Када су карте сортиране по рангу са стабилним сортирањем, две петице морају остати у оригиналном редоследу, као што су и ушле. Када су сортиране са нестабилним сортирањем, петице губе свој оригинални редослед. Када се сортира нека врста података, само део података се испитује при одређивању редоследа. На примеру са сортирањем карата, у картици са десне стране се вид да су карте сортиране према њиховом рангу, а њихова боја се игнорише. Ово даје могућност вишеструких различитих верзија сортирања оригиналне листе. Алгоритми стабилног сортирања се према следећем правилу: ако две ставке упореди као једнаке (као што су две карте петице) онда ће њихов релативни редослед бити сачуван, тако да ако једна дође пре осталих, онда ће и да изађе пре осталих.
Формалније речено, сортирани подаци могу бити представљени као запис или као вредности енторке, а део података који се користи за сортирање се зове кључ. У примеру са картама, карте су представљене као вредност (ранг, исте боје) а кључ је ранг. Алгоритам за сортирање је стабилан кад год постоје две вредности П и С са истим кључем, и П појави пре С у првобитном списку, онда П остаје испред С у сортираној листи.
Стабилност не представља проблем када се елементи могу разликовати, као што је код целих бројева, или уопште сви подаци где су сви елементи кључ, стабилност не представља проблем. Стабилност такође није проблем ако су сви кључеви различити.
Нестабилни алгоритми сортирања могу бити прерађени у стабилне. Један од начина да се то уради је да се вештачки продужи поређење кључева, тако да поређења између два објекта са једнаким кључевима користе редослед уноса у оригиналним улазној листи као у "тај-брејку". Међутим, памћење ове наредбе може да захтева додатно време и простор.
Једна апликација за стабилне алгоритме сортирања, сортира листу користећи примарни и секундарни кључ. На пример, желимо да сортирамо карте из руке по бојама и то по редоследу: детелина (♣), каро (♦), срце (♥), пик (♠), а унутар сваког знака, карте буду сортиране по рангу. Ово се може урадити тако што се прво сортирају карте по рангу (користећи било какво сортирање), а затим ради стабилно сортирање знакова:
400x400px
Унутар сваког знака, стабилно сортирање чува редослед по рангу, које је већ урађено. Ова идеја се може проширити на било који број кључева, а урађено је уз помоћ основног сортирања. Исти ефекат се може постићи и са нестабилним сортирањем помоћу поређења лексико-графичких кључева, које на пример пореди прво знакове, а затим упоређује по рангу ако су знакови исти.
Поређење алгоритама У овој табели, је н број вредности које треба да се сортирају. Колоне "Просечна" и "Најгора" дају сложеност времена у сваком случају, под претпоставком да је дужина сваког кључа константна и да стога сва поређења, размене и остале потребне операције могу да се наставе у константном времену. "Меморија" означава количину помоћног складишта потребног за даље коришћење самог списка, под истом претпоставком. Листа захтева времена и меморије се сматра дефинисаним у оквиру дефиниције "велико О". Логаритми су по било ком основу; ознака значи .
Ово су све поређења сортирања, па се не може извршити брже од O(n log n) у просечном и најгорем случају. + Поређење сортирања НазивНајбољи Просек НајгориМеморијаТабела Метода Остали подациБрзо сортирање 15 ! 20 ! 25 ! 05 ! просек, најгори случај је ; "Седвик" варијација је најгори случај типично "на месту" није стабилно; стабилне верзије постоје Подела Брзо сортирање се углавном извршава "на месту" са O(лог н) "стек" простора. Већина имплементација су нестабилне, како је стабло на место партиционисања сложеније. Варијанте Алгоритма користе O(n) места да сачувају партицију. Брза варијанта користи троструку (ФАТ) поделу узима О (н) поређења када је сортирање низ једнаких кључева.Спајање 20 ! 20 ! 20 ! 15 ! Да Спајање Високо паралелизовано (up to O(log n) користи три Мађара алгоритамAjtai, M.; Komlós, J.; Szemerédi, E. (1983). или практичније речено, Колово паралелно спајање за обраду велике количине података."На месту" спајање — — 23 ! 00 ! Да Спајање Може бити имплементирано као стабилно на основу стабилног "на месту" спајања. Нагомилано сортирање 20 ! 20 ! 20 ! 00 ! Не Селекција Уметање 15 ! 25 ! 25 ! 00 ! Да Уметање O(н + д), у најгорем случају преко секвенци које имају д инверзије. Унутрашње сортирање 20 ! 20 ! 20 ! 05 ! Не Подела и Селекција Користи се у СТШ имплементацијама. Селективно сортирање 25 ! 25 ! 25 ! 00 ! Не Селекција Стабилно са O(н) додатног простора, на пример помоћу листе." Тимсорт" 15 ! 20 ! 20 ! 15 ! Да Уметање и Спајање Тражи н поређења када су подаци већ сортирани или се обрнуто сортирају.Кубно сортирање 15 ! 20 ! 20 ! 15 ! Да Уметање Тражи н поређења када су подаци већ сортирани или се обрнуто сортирају. Сортирање љуске 15 ! 23 !or 23 !Depends on gap sequence;
best known is 00 ! Не Уметање Мале величина код, без употребе "стека", разумно брзо, корисно где је меморија битна као што су уграђене и старије апликације. Мехурасто сортирање 15 ! 25 ! 25 ! 00 ! Да Размена Веома мале величине код.Бинарно гранање 15 ! 20 ! 20 ! 15 ! Да Уметање Када се користи самобалансирајуће бинарно стабло претраге. Кружно сортирање 25 ! 25 ! 25 ! 00 ! Не Уметање "На месту" са теоријски оптималним бројем уноса.Складиштно сортирање 15 ! 20 ! 25 ! 15 ! Да Уметање Стрпљиво сортирање 15 ! — 20 ! 15 ! Не Уметање и Селекција Тражи све најдуже растуће поднизове у O(н log н). Глатко сортирање 15 ! 20 ! 20 ! 00 ! Не Селекција Адаптивно сортирање: поређења када се подаци већ сортирају и 0 размене.Штранд 15 ! 25 ! 25 ! 15 ! Да Селекција"Турнир" 20 ! 20 ! 20 ! 15 ! Не Селекција Варијанта нагомиланог сортирања."Коктел" 15 ! 25 ! 25 ! 00 ! Да РазменаКомбиновано 15 ! 15 ! 25 ! 00 ! Не Размена Код мале величине.Гном 15 ! 25 ! 25 ! 00 ! Да Размена Код веома мале величине.Немешовито 15 ! 25 ! 25 ! 00 !"На месту" за линковане листе. НеДистрибуција и СпајањеНе изводе се размене. Параметар 'к' је пропорционалан ентропији која се уноси. К = 1 за одређено до напред или отпозади. Франчинијев метод — 20 ! 20 ! 00 ! Да?Блокада 15 ! 20 ! 20 ! 00 ! Да Уметање и Спајање Комбинује се блок O(н) "на месту" спаја алгоритам са одоздо према горе спајањем.Необично сортирање 15 ! 25 ! 25 ! 00 ! Да Размена Може се лако пустити у паралелне процесе. Следећа табела описује алгоритме целобројног сортирања и других алгоритама за сортирање који не користе упоређивање. Као такви, они нису ограничени на доњу границу. Претпоставља се да је сложеност н ставки да се сортирају, са кључевима величине к, цифре величине д и р распон бројева који треба да се сортирају. Многе од њих су засноване на претпоставци да је кључна величина довољно велика да све ставке имају јединствене кључне вредности, а самим тим и да n << 2k, где<< значи "много мање од". +Без поређења НазивНајбољи Просек Најгори МеморијаСтабилан n << 2k БелешкеПретинац — Да ДаСегментно(означени кључеви) — Да Не Поставља равномерну расподелу елемената из домена у низу. .Сегментно(целобројни кључеви) — Да Да Ако р је O(н), онда је Просек O(н).Бројење — Да Да Ако р је O(н), онда је Просек O(н).ЛСД Основно — Да Не МСД Основно — Да Не Стабилна верзија користи екстерни низ величине н и држи све ставке.МСД Основно ("на месту") — Не Не ниво рекурзије, 2d за бројање низа.Раздвојено сортирање — Не Не Asymptotic are based on the assumption that n << 2k, but the algorithm does not require this.Избијање — Не Не Има бољи константан фактор него основно сортирање за сортирање ниских. Иако се донекле ослања на специфичности често су се јављале ниске."Флеш" Може бити стабилан са додатним простором Не Захтева равномерну расподела елемената из домена у низ да би радио у линеарном времену. Ако је дистрибуција изузетно мимоилазно онда може ићи квадратна ако је основа квадратна (обично је врста уметање). "На месту" верзија није стабилна."Поштар" — — Да Варијација сегментног, који ради веома слично МСД-у Основног. Специфична за постављање потребних услуга.