Алгоритми сортирања

Алгоритам сортирања је алгоритам  који ставља елементе листе у одређеном редоследу. Највише коришћена наређења су нумерички и лексичко-графички ред. Ефикасно сортирање је важно за оптимизацију коришћења других алгоритама (као што су алгоритми претраге и спајања) које захтевају унос података у сортиране листе; такође је често корисно за "канонизоване" податаке и за производњу људски разумљивих излазних вредности. Формалније речено, излаз мора задовољити два услова:

1. Излаз је у растућем редоследу (сваки елемент је већи од претходног елемента према жељеном редоследу);
2. Излаз је пермутација (преуређена) улаза.

Даље, подаци се радије узимају да буду низ, који омогућава насумичан приступ, него листа која дозвољава само секвенцијални приступ, мада често алгоритми се могу примењивати уз погодну модификацију за обе врсте података.

Од настанка рачунарства, проблем сортирања је привукао велика истраживања, можда због сложености његовог ефикасног решавања упркос свом једноставном обрачун. На пример, "мехурасто сортирање" је анализиран већ 1956. године.^[1] Основна граница сортирања поређења алгоритама је да они захтевају време извршавања – O(n log n) – у најгорем случају, мада боље перформансе је могуће извести на стварним подацима (као што су сортирани подаци), и алгоритама који нису основани на поређењу, као што је бројање врсти, могу имати боље перформансе. Иако многи сматрају сортирање као решен проблем - асимптотично оптимални алгоритми су познати још од средине 20. века – корисни нови алгоритми се још увек праве са сада већ увелико коришћеним тимсорт из 2002. године, и библиотечко сортирање које се први пут појавило 2006. године.

Алгоритми сортирања су распрострањени у уводу информатике, где обиље алгоритама за проблем пружа благи увод у разне концепте алгоритма као што су " велико О", подели па владај алгоритми, структуре података као што су гомиле и бинарна стабла, "случајни алгоритми", анализа најбољи, најгори и просечан случај, компромиси временског простора, као и горња и доња граница.

Класификација

Алгоритми сортирања се често деле по:

• Комплексности (најгоре, просечно и најбоље понашање) поређења елемената у смислу величине листе (н). За типичне алгоритме сортирања, добро понашање је O(n log n), са паралелним сортирањем је O(log2 n), а најгоре је О(n²). (погледај "велико О") Идеално понашање за серијско сортирање је O(n), али ово није могуће у просечном случају. Најповољније за паралелно сортирање је O(log). Поређење сортирања алгоритама, које процењује елементе листе путем апстрактног кључног поређења рада захтева најмање O (n log n) поређења за већину улазних вредности.
• Сложеност размене (за "на месту" алгоритама).
• Меморијска искоришћеност (и коришћење других рачунарских ресурса). Посебно, неки алгоритми за сортирање су "на месту". "На месту" врсте захтева само О (1) меморије изван ставки које су сортиране; Понекад се O (log (n)) додатне меморије сматра "на месту".
• Рекурзија. Неки алгоритми су или рекурзивни или не-рекурзивни, док други могу бити оба (нпр. интегрисано сортирање).
• Стабилност: стабилни алгоритми за сортирање одрже релативан ред записа са једнаким кључевима (тј. вредностима).
• Без обзира да ли је то сортирање поређењем или не. Сортирање поређењем испитује податке само поређењем два елемента са оператором поређења.
• Општи метод: уметање, размена, избор, спајање, итд. Сортирање разменом се састоји из мехурастог и брзог сортирања. Селективно сортирање чине мешовито и нагомилано сортирање. Такође, ту се гледа да ли је серијско или паралелно. Остатак ове дискусије се готово искључиво концентрише на серијске алгоритме и серијски рад.
• Прилагодљивост: Да ли преуређеност од улаза утиче или не на време рада. Алгоритми који се узимају у обзир су адаптивни.

Стабилност

Пример стабилног сортирање на картама. Када су карте сортиране по рангу са стабилним сортирањем, две петице морају остати у оригиналном редоследу, као што су и ушле. Када су сортиране са нестабилним сортирањем, петице губе свој оригинални редослед.

Када се сортира нека врста података, само део података се испитује при одређивању редоследа. На примеру са сортирањем карата, у картици са десне стране се вид да су карте сортиране према њиховом рангу, а њихова боја се игнорише. Ово даје могућност вишеструких различитих верзија сортирања оригиналне листе. Алгоритми стабилног сортирања се према следећем правилу: ако две ставке упореди као једнаке (као што су две карте петице) онда ће њихов релативни редослед бити сачуван, тако да ако једна дође пре осталих, онда ће и да изађе пре осталих.

Формалније речено, сортирани подаци могу бити представљени као запис или као вредности енторке, а део података који се користи за сортирање се зове кључ. У примеру са картама, карте су представљене као вредност (ранг, исте боје) а кључ је ранг. Алгоритам за сортирање је стабилан кад год постоје две вредности П и С са истим кључем, и П појави пре С у првобитном списку, онда П остаје испред С у сортираној листи.

Стабилност не представља проблем када се елементи могу разликовати, као што је код целих бројева, или уопште сви подаци где су сви елементи кључ, стабилност не представља проблем. Стабилност такође није проблем ако су сви кључеви различити.

Нестабилни алгоритми сортирања могу бити прерађени у стабилне. Један од начина да се то уради је да се вештачки продужи поређење кључева, тако да поређења између два објекта са једнаким кључевима користе редослед уноса у оригиналним улазној листи као у "тај-брејку". Међутим, памћење ове наредбе може да захтева додатно време и простор.

Једна апликација за стабилне алгоритме сортирања, сортира листу користећи примарни и секундарни кључ. На пример, желимо да сортирамо карте из руке по бојама и то по редоследу: детелина (♣), каро (♦), срце (♥), пик (♠), а унутар сваког знака, карте буду сортиране по рангу. Ово се може урадити тако што се прво сортирају карте по рангу (користећи било какво сортирање), а затим ради стабилно сортирање знакова:

Унутар сваког знака, стабилно сортирање чува редослед по рангу, које је већ урађено. Ова идеја се може проширити на било који број кључева, а урађено је уз помоћ основног сортирања. Исти ефекат се може постићи и са нестабилним сортирањем помоћу поређења лексико-графичких кључева, које на пример пореди прво знакове, а затим упоређује по рангу ако су знакови исти.

Поређење алгоритама

У овој табели, је н број вредности које треба да се сортирају. Колоне "Просечна" и "Најгора" дају сложеност времена у сваком случају, под претпоставком да је дужина сваког кључа константна и да стога сва поређења, размене и остале потребне операције могу да се наставе у константном времену. "Меморија" означава количину помоћног складишта потребног за даље коришћење самог списка, под истом претпоставком. Листа захтева времена и меморије се сматра дефинисаним у оквиру дефиниције "велико О". Логаритми су по било ком основу; ознака  ${\displaystyle \log ^{2}n}$ значи ${\displaystyle (\log n)^{2}}$.

Ово су све поређења сортирања, па се не може извршити брже од O(n log n) у просечном и најгорем случају.

Поређење сортирања

Назив	Најбољи	Просек	Најгори	Меморија	Табела	Метода	Остали подаци
Брзо сортирање	15 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	25 !${\displaystyle n^{2}}$	05 !${\displaystyle \log n}$ просек, најгори случај је ${\displaystyle n}$; "Седвик" варијација је ${\displaystyle \log n}$ најгори случај	типично "на месту" није стабилно; стабилне верзије постоје	Подела	Брзо сортирање се углавном извршава "на месту" са O(лог н) "стек" простора. Већина имплементација су нестабилне, како је стабло на место партиционисања сложеније. Варијанте Алгоритма користе O(n) места да сачувају партицију. Брза варијанта користи троструку (ФАТ) поделу узима О (н) поређења када је сортирање низ једнаких кључева.
Спајање	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$	Да	Спајање	Високо паралелизовано (up to O(log n) користи три Мађара алгоритам[2] или практичније речено, Колово паралелно спајање за обраду велике количине података.
"На месту" спајање	—	—	23 !${\displaystyle n\log ^{2}n}$	00 !${\displaystyle 1}$	Да	Спајање	Може бити имплементирано као стабилно на основу стабилног "на месту" спајања.[3]
Нагомилано сортирање	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	00 !${\displaystyle 1}$	Не	Селекција
Уметање	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Да	Уметање	O(н + д), у најгорем случају преко секвенци које имају д инверзије.
Унутрашње сортирање	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	05 !${\displaystyle \log n}$	Не	Подела и Селекција	Користи се у СТШ имплементацијама.
Селективно сортирање	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Не	Селекција	Стабилно са O(н) додатног простора, на пример помоћу листе.[4]
" Тимсорт"	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$	Да	Уметање и Спајање	Тражи н поређења када су подаци већ сортирани или се обрнуто сортирају.
Кубно сортирање	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$	Да	Уметање	Тражи н поређења када су подаци већ сортирани или се обрнуто сортирају.
Сортирање љуске	15 !${\displaystyle n}$	23 !${\displaystyle n\log ^{2}n}$ or ${\displaystyle n^{3/2}}$	23 !Depends on gap sequence; best known is ${\displaystyle n\log ^{2}n}$	00 !${\displaystyle 1}$	Не	Уметање	Мале величина код, без употребе "стека", разумно брзо, корисно где је меморија битна као што су уграђене и старије апликације.
Мехурасто сортирање	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Да	Размена	Веома мале величине код.
Бинарно гранање	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n~{\text{(balanced)}}}$	15 !${\displaystyle n}$	Да	Уметање	Када се користи самобалансирајуће бинарно стабло претраге.
Кружно сортирање	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Не	Уметање	"На месту" са теоријски оптималним бројем уноса.
Складиштно сортирање	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	25 !${\displaystyle n^{2}}$	15 !${\displaystyle n}$	Да	Уметање
Стрпљиво сортирање	15 !${\displaystyle n}$	—	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$	Не	Уметање и Селекција	Тражи све најдуже растуће поднизове у O(н log н).
Глатко сортирање	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	00 !${\displaystyle 1}$	Не	Селекција	Адаптивно сортирање: ${\displaystyle n}$ поређења када се подаци већ сортирају и 0 размене.
Штранд	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	15 !${\displaystyle n}$	Да	Селекција
"Турнир"	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$[5]	Не	Селекција	Варијанта нагомиланог сортирања.
"Коктел"	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Да	Размена
Комбиновано	15 !${\displaystyle n}$	15 !${\displaystyle n\log n}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Не	Размена	Код мале величине.
Гном	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Да	Размена	Код веома мале величине.
Немешовито[6]	15 !${\displaystyle kN}$	25 !${\displaystyle kN}$	25 !${\displaystyle kN}$	00 !"На месту" за линковане листе.	Не	Дистрибуција и Спајање	Не изводе се размене. Параметар 'к' је пропорционалан ентропији која се уноси. К = 1 за одређено до напред или отпозади.
Франчинијев метод[7]	—	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	00 !${\displaystyle 1}$	Да	?
Блокада	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	00 !${\displaystyle 1}$	Да	Уметање и Спајање	Комбинује се блок O(н) "на месту" спаја алгоритам[8] са одоздо према горе спајањем.
Необично сортирање	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Да	Размена	Може се лако пустити у паралелне процесе.

Следећа табела описује алгоритме целобројног сортирања и других алгоритама за сортирање који не користе упоређивање. Као такви, они нису ограничени на ${\displaystyle \Omega (n\log n)}$ доњу границу. Претпоставља се да је сложеност н ставки да се сортирају, са кључевима величине к, цифре величине д и р распон бројева који треба да се сортирају. Многе од њих су засноване на претпоставци да је кључна величина довољно велика да све ставке имају јединствене кључне вредности, а самим тим и да n << 2^k, где<< значи "много мање од".

Без поређења

Назив	Најбољи	Просек	Најгори	Меморија	Стабилан	n << 2^k	Белешке
Претинац	—	${\displaystyle n+2^{k}}$	${\displaystyle n+2^{k}}$	${\displaystyle 2^{k}}$	Да	Да
Сегментно(означени кључеви)	—	${\displaystyle n+k}$	${\displaystyle n^{2}\cdot k}$	${\displaystyle n\cdot k}$	Да	Не	Поставља равномерну расподелу елемената из домена у низу.[9]
Сегментно(целобројни кључеви)	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	Да	Да	Ако р је O(н), онда је Просек O(н).[10]
Бројење	—	${\displaystyle n+r}$	${\displaystyle n+r}$	${\displaystyle n+r}$	Да	Да	Ако р је O(н), онда је Просек O(н).[9]
ЛСД Основно	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	Да	Не	[9][10]
МСД Основно	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	Да	Не	Стабилна верзија користи екстерни низ величине н и држи све ставке.
МСД Основно ("на месту")	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle 2^{d}}$	Не	Не	${\displaystyle {\frac {k}{d}}}$ ниво рекурзије, 2^d за бројање низа.
Раздвојено сортирање	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot \left({{\frac {k}{s}}+d}\right)}$	${\displaystyle {\frac {k}{d}}\cdot 2^{d}}$	Не	Не	Asymptotic are based on the assumption that n << 2^k, but the algorithm does not require this.
Избијање	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	Не	Не	Има бољи константан фактор него основно сортирање за сортирање ниских. Иако се донекле ослања на специфичности често су се јављале ниске.
"Флеш"	${\displaystyle n}$	${\displaystyle n+r}$	${\displaystyle n^{2}}$	${\displaystyle n}$	Може бити стабилан са ${\displaystyle O(n)}$ додатним простором	Не	Захтева равномерну расподела елемената из домена у низ да би радио у линеарном времену. Ако је дистрибуција изузетно мимоилазно онда може ићи квадратна ако је основа квадратна (обично је врста уметање). "На месту" верзија није стабилна.
"Поштар"	—	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n\cdot {\frac {k}{d}}}$	${\displaystyle n+2^{d}}$	—	Да	Варијација сегментног, који ради веома слично МСД-у Основног. Специфична за постављање потребних услуга.

Примерно сортирање се може паралелно користити са неким сортирањем које не користи поређење, и притом ефикасно дистрибуира податке на више различитих сегмената и онда их пропушта даље, сортирајући их у неколико процеса без потребе да се поново деле јер су већ међусобно сортирани.

Следећа табела описује неке алгоритме за сортирање који су непрактични за употребу у ствраној ситуацији због изузетно лошег учинка или специјализованих хардверских захтева.

Назив	Најбољи	Просек	Најгори	Меморија	Стабилан	Поређење	Остали подаци
"Нишан"	15 !${\displaystyle n}$	23 !${\displaystyle S}$	23 !${\displaystyle S}$	25 !${\displaystyle n^{2}}$	Н/А	Не	Ради само са позитивним целим бројевима. Захтева специјализован хардвер за рад у загарантовано О (н) време. Постоји могућност за имплементацију софтвера, али рад времена ће бити О (С), где је С скуп свих целих бројева који се сортирају, у случају малих целих бројева може се сматрати да је линеарна.
Једноставно сортирање	—	15 !${\displaystyle n}$	15 !${\displaystyle n}$	05 !${\displaystyle \log n}$	Не	Да	Бројање је број пролаза.
Анкетно	15 !${\displaystyle n}$	15 !${\displaystyle n}$	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	Да	Бирање	Ово је линеарно времен, аналогни алгоритам за сортирање низ ставки, захтевајући О ( н ) стек простора, а сортирање је стабилно. Ово захтева н паралелних процеса. Види Шпагетно сортирање.
Сортирање мреже	06 !${\displaystyle \log ^{2}n}$	06 !${\displaystyle \log ^{2}n}$	06 !${\displaystyle \log ^{2}n}$	21 !${\displaystyle n\log ^{2}n}$	Разликује (мреже стабилног сортирања захтевају више поређења)	Да	Редослед поређења је унапред постављен на основу одређене величине мреже. Непрактично је за више од 32 артикла.
Битоник поређење	06 !${\displaystyle \log ^{2}n}$	06 !${\displaystyle \log ^{2}n}$	06 !${\displaystyle \log ^{2}n}$	21 !${\displaystyle n\log ^{2}n}$	Не	Да	Ефикасна варијација Сортирања мреже.
"Глупо" сортирање	15 !${\displaystyle n}$	99 !${\displaystyle n\cdot n!}$	99 !${\displaystyle \infty }$	00 !${\displaystyle 1}$	Не	Да	Разна мешања. Користи се за пример саме сврхе, као и сортирање у најгорем случају истеклог времена.
Марионета	30 !${\displaystyle n^{\log 3/\log 1.5}}$	30 !${\displaystyle n^{\log 3/\log 1.5}}$	30 !${\displaystyle n^{\log 3/\log 1.5}}$	15 !${\displaystyle n}$	Не	Да	Спорије него већина алгоритама за сортирање са временом од сложености O(n^log 3 / log 1.5) = O(n^2.7095.^..).

Теоријски компјутерски научници су детаљно пручили друге алгоритме сортирања који омогућавају боље од O(n log n) комплексност времена преузимања додатних ограничења, укључујући:

• Ханов алгоритам, детерминистички алгоритам за сортирање кључева из области коначне величине, узимајући O(n log log n) времена и O(n) простора.
  ^[11]
• Торупов алгоритам, насумичан алгоритам за сортирање кључева из области коначне величине, узимајући O(n log log n) времена и O(n) простора.
• ^[12]
• Насумични алгоритам целобројног сортирања захтева време и O(n) места.
  ^[13]

Популарни алгоритми сортирања

Иако постоји велики број алгоритама за сортирање, у практичном имплементација неколико алгоритама доминира. Сортирање убацивањем се користи за мале скупове података, док се за велике податаке поставља асимптотски ефикасно сортирање користи пре свега нагомилано, спајањем или брзо сортирање. Ефикасне имплементације углавном користи хибридни алгоритам, комбиновањем асимптотски ефикасан алгоритам за укупно сортирање са уносним за мале листе на дну рекурзије. Високо регулисане имплементације користе софистицираније варијанте, као што су Тимсорт (спајајуће, уносно сортирање и додатна логика), који се користи у Андроиду, Јави и Пајтону, док се уводно (брзо и нагомилано сортирање) користи (у варијанти облика) у неким C++ сортирањима имплементације и у . НЕТ.

За више ограничених података, као што су бројеви у фиксном интервалу, у широкој употреби су дистрибуцијска сортирања као што су бројиво или основно сортирање. Мехурасто сортирање и разне варијанте се ретко користе у пракси, али се често срећу у настави и теоријским расправама.

За физичко сортирање објектата, као што су алфабетизовани папири (тестови или књиге), људи интуитивно користе углавном уносно сортирање за мале скупове. За веће скупове, где је први сегмент као што је почетном слово и вишеструке сегменте омогућава практичну сортирање веома великих скупова. Често је простор релативно јефтин, као што је ширење објеката на поду или на великој површини, али операције су скупе, посебно померање предмета велике удаљености - локалитет референца је важан. Спајање је практично за физичке објекте, нарочито може да се користи као две руке, по једна за сваку листу да споји, док су остали алгоритми као што су нагомилавање или брзо сортирање слабо погодне за људску употребу. Други алгоритми, као што су складиштно или варијанта уносног сортирања која оставља простор, такође су практични за физичку коришћење.

Једноставно сортирање

Два најједноставнија сортирања су уносно и селективно, оба су ефикасна са малим податцима због малих трошкова, али нису за велике податаке. Уносно сортирање је генерално брже од селективног у пракси, због мањег поређења и добре перформансе на скоро сортираним податацима и због тога се препоручује у пракси, али селективно се мање пише, и на тај начин се користи када су перформансе писања ограничавајући фактор.

Уметање

Уносно сортирање је алгоритам једноставног сортирања који је релативно ефикасан за мале листе и углавном сортиране листе, и често се користи као део софистициранијих алгоритама. Ради по принципу узимања елемената из листе једног по једног и постављања у њихов правилан положај у новој сортираној листи.^[14] У низовима, нова листа и преостали елементи могу поделити простор низа, али уметање је скупо и захтева померање свих наредних елемената због једног. Сортирање љуске (види доле) је варијанта уносног који је ефикаснији за веће листе.

Селекција

Селективно сортирање је "на месту" сортирање поређењем. Има O(n²) комплексност, што га чини неефикасним за велике листе и генерално је лошији од сличног уметања. Селективно сортирање је познато по својој једноставности, а такође има предности у перформансама у односу на компликованије алгоритме у одређеним ситуацијама.

Алгоритам проналази минималну вредност, мења га са вредношћу на првој позицији и понавља ове кораке за остатак листе.^[15] То не чини ништа више од н замена и на тај начин је користан када је премештање веома скупо.

Ефикасно сортирање

Практично опште сортирање алгоритама је скоро увек засновано на алгоритму који има просечну сложеност (и уопште у најгорем случају) O(н лог н), од којих су најчешћи су нагоммилано, спајајуће и брзо сортирање. Сваки има своје предности и мане, међу којима је најзначајнија једноставна имплементација спајања која захтева O(н) додатног простора, а једноставна имплементација брзог сортирања има O(н²) у најгорем случају сложености. Ови проблеми се могу решити или ублажити уз помоћ сложенијег алгоритма.

Иако су ови алгоритми асимптотski ефикасни на случајним подацима, за практичну ефикасност на реалним подацима се користе разне модификације. Прво, граница ових алгоритама постаје значајна на мањим подацима, тако да се чешће користи хибридни алгоритам, обично прелажењем на уметање када су подаци довољно мали. Друго, алгоритми се слабије користе на већ разврстаним или готово сортираним подацима - то је уобичајено у реалним подацима и могу бити сортирани у O(н) време за одговарајуће алгоритме. На крају, они могу бити нестабилни, а стабилност је често пожељна особина у сортирању. Често се користе софистициранији алгоритми, као што су Тимсорт (на основу спајања) или унутрашње (на основу брзог, враћајући се у нагомилано сортирање).

Спајање

Ова врста има предност због лакоће спајања већ сортираних листи у нову сортирану листу. Почиње поређењем свака два елемента (нпр. 1 и 2, потом 3 и 4...) и замене места ако је то потребно. Онда спаја све добијене листе од по два члана у четворочлане листе и тако даље; док се последње две листе сортиране у финалну сортирану листу.^[16] Од свих овде описаних алгоритама, ово је прва која веома добро функционишу са великим листама, јер је њен најгори случај у времену O(н лог н). Такође се лако уноси у листе, не само у низове, јер захтева само редни, а не случајан приступ. Међутим, има додатну O(н) просторну сложеност, и укључује велики број копија у једноставним имплементацијама.

Спајање је релативно скоро добило на популарности за практичне имплементације, због њеног коришћења у софистицираном алгоритму Тимсорт, које се користи за стандардне методе сортирања у програмским језицима Пајтон^[17] и Јава (као и ЈДК7^[18]). Спајање је сама стандарна рутина у Перл,^[19] између осталог, и коришћена је у Јави барем од 2000. у ЈДК1.3.^[20][21]

Нагомилавање

Нагомилавање је много ефикаснија верзија од селекције. Такође, ради по принципу одређивања највећег (или најмањег) елемента у листи, стављајући га на крај (или почетак) листе и наставља са остатком листе, при том остварује овај задатак ефикасно користећи структуру података званом "нагомилавање", која је посебна врста бинарног стабла.^[22] Када је листа података направљена, чвор је сигурно највећи (или најмањи) елемент. Када је уклоњена и стављена на крају листе, гомила је преуређена тако да је највећи елеменат преосталих потеза код корена. Користећи овај начин, време за претраживање највећег члана је O(лог н), уместо O(n) за линеарно скенирање код селекције. Ово дозвољава нагомилавању O(н лог н) времена и ово је уједно и најгори могући случај.

Брзо сортирање

Брзо сортирање је подели па владај алгоритам који се ослања на партицију рада: на изабрану партицију низа елемента познатијег као пивот.^[23][24] Сви елементи мањи од пивота се стављају испред њега и сви веће елементи иза њега. Ово се може ефикасно урадити у линеарном времену и "на месту". Мање и веће подлисте су рекурзивно сортиране. Ово даје просечну комплексност времена О (н лог н), са ниским границама и на тај начин је ово популаран алгоритам. Ефикасни имплементације брзог сортирања (са "на месту" поделом) су обично нестабилне и помало сложене, али су међу алгоритмима најбрже сортирање у пракси. Са својим скромним О (лог н) додатног простора, брзо сортирање је једно од алгоритама најпопуларнијих сортирања и најдоступнијих у стандардним програмским библиотекама.

За брзо сортирање је важно да је најгори случај O(н²); што је ретка појава, у наивним имплементацијама (избор први или последњи елемент као пивот) се ово често дешава због издвојених података. Најсложенији проблем је начин одабира доброг пивота, јер доследно лоши избори стожера могу довести до драстично споријих O(н²) перформанси, али добар избор стожера даје О (н лог н), која је асимптотски одговарајућа. На пример, ако је на сваком кораку средња вредност изабрана као стожер онда алгоритам ради у О (н лог н). Проналажење средње вредности, као што је код средње вредности селекције алгоритма је О (н) операција на не-сортираним листама и самим тим узима значајан део границе са сортирањем. У пракси бирање случајног пивота готово сигурно даје O(н лог) перформансе.

Мехурасто сортирање и варијанте 

Мехурасто сортирање и варијанте као што су "коктели", су једноставна, али веома неефикасна сортирања. Они се често могу видети у уводним текстовима и имају неке теоријске интересе због једноставности анализе, али се ретко користе у пракси, а пре свега због рекреативног интереса. Неке варијанте попут сортирања љуске имају отворена питања о њиховом понашању.

Мехурасто сортирање

Мехурасти алгоритам за сортирање иде континуирано кроз листу и мења ставке све док се не појаве у исправном редоследу.

Мехурасто сортирање је једноставно сортирање алгоритма. Алгоритам почиње на почетку сета података. Упоређује прва два елемента и ако је први већи од другог, онда им мења места. Овим принципом наставља да ради на сваком пару суседних елемената до краја сета података. Затим поново почиње са прва два елемента, понављајући ово све док има потребе за заменом места елемената.^[25] Просек и најгори учинак овог алгоритма је O(н²), тако да се ретко користи за сортирање великих, несређених сетова података. Мехураст принцип се може користити за сортирање малог броја ствари (где асимптотска неефикасност није толико битна). Такође се може ефикасно користити на листи било које дужине која је скоро сортирана (то јест, елементи нису значајно измешани). На пример, ако било који број елемената је изван свог места, помоћу само једне позиције (нпр. 0123546789 и 1032547698), мехурасто сортирање ће их наћи у првом пролазу, а у другом ће их поставити на своје место, тако да ће трајати само 2н.

Сортирање љуске

Љуска се од мехура разликује по бројним потезима, којима премешта елементе на позиције. 

Сортирање љуске је направио Доналд Шел 1959. Побољшана мехурасто сортирање и уметање, уз помоћ обављања више функција премештања истовремено. Једна имплементација може се описати као уређење секвенце података у дводимензионалном низу, а затим сортирање колоне низа користећи уметање.

Комбиновано сортирање

Комбиновано сортирање је једноставан алгоритам сортирања, који је дизајнирао Влодцимрц Добошиевич 1980.^[26] Касније су поново открили и популаризовали Стефан Лаци и Ричард Бокс у Бајт Магазину, у чланку објављеном априла 1991. године. Комбиновано сортирање је помогло у побољшању мехурастог. Основна идеја је да се елиминишу "корњаче", то јест мале вредности на крају листе, јер је мехурасто сортирање страховито споро. ("Зечеви", велике вредности које се налазе на почетку листе, не представљају проблем мехурастом сортирању)

Дистрибутивно сортирање

Дистрибутивно сортирање се односи на било који алгоритам за сортирање у којем се подаци дистрибуирају са свог места на више средњих структура које се онда окупљају и штампају. На пример сегментно и "флеш" сортирање су алгоритми за сортирање засновани на бази дистрибуције. Дистрибутивни алгоритам сортирања се може користити у једном процесу или може бити дистрибуирани алгоритам, где се појединачне подгрупе одвојено сортирају у различитим процесима, па онда комбинују. Ово омогућава спољно сортирање података који су превелики да би стали у меморију једног рачунара.

Бројање

Бројање се примењује када се сваки за улаз зна да припада одређеном склопу С могућности. Алгоритам ради у O(|С| + н) времену и O(|С|) меморији где је н дужина уноса. Ради стварањем целобројног низа величине |С| и користи и-ти број да изброји случајеве и-тог члана С склопа. Сваки улаз је израчунат од стране увећаних вредности одговарајућег склопа. Након тога, бројање низа се извршава кроз петљу како би се све вредности поређале. Овај алгоритам се често не може користити, јер С мора да буде разумно мали да би алгоритам био ефикасан, али је изузетно брз и показује асимптотско понашање како се н повећава. Он такође може бити модификован да омогућава стабилно понашање.

Сегментно сортирање

Сегментно сортирање је Подели па владај алгоритам сортирања који уопштава бројање дељењем низа у коначан број сегмената. Сваки сегмент је сортиран појединачно или користећи други алгоритам сортирања или рекурзивно применом сегментног алгоритма.

Сегментно сортирање најбоље ради када су елементи скупа података равномерно распоређени по свим сегментима.

Основно сортирање

Основно сортирање је алгоритам који сортира бројеве прерадом појединачне цифре. Бројеви н који се састоје од к цифара се сортирају у O(н · к) времену. Ова врста сортирања може да преради цифре сваког броја или почев од цифре најмањег значаја (ЛСД) или почев од најзначајније цифре (МСД). ЛСД алгоритам прво сортира списак према цифри најмањег значаја чувајући њихов релативни редослед користећи стабилно сортирање. Онда сортира следећу цифру и тако даље, све док се списак не сортира од најмање значајне до најзначајније цифре. Док ЛСД захтева коришћење стабилног сортирања, МСД алгоритам то не тражи (осим ако је стабилно сортирање пожељно). "На месту" МСД сортирање није стабилно. То је уобичајено за бројање да буде интерно коришћено од стране основног. Хибридно сортирање приступа као и коришћење уметања за мале склопове података при чему се значајно побољшавају перформансе основног сортирања.

Обрасци коришћења меморије и сортирање индекса

Када је величина низа за сортирање приближна или премашује расположиву примарну меморију, тако да (много спорије) диск или размена простора мора бити заузета, образац употребе меморије алгоритма постаје важан и алгоритам који може бити прилично ефикасан када је низ лако уклапа у РАМ, може да постане непрактичан. У овој ситуацији, укупан број поређења постаје (релативно) мање важан, а број делова из меморије и са диска који се мора копирати или заменити могу да доминирају перформансе карактеристичне алгоритму. Тако број пролаза и локализација поређења може бити важнији од сировог броја поређења, јер се поређења околних елемената један са другим обављају у магистралама (или у кеш меморији, чак и при брзини процесора), што је у односу на брзину диска практично гледано тренутна.

На пример, популарно рекурзивно брзо сортирање даје прилично разумне перформансе са адекватним РАМ-ом, али због рекурзивног начина да се копирају делови низа, постаје мање практично када се низ не уклапа у РАМ, јер то може изазвати низ спорих поступака са диска. У том случају, може бити пожељан, чак и ако је потребно више укупних поређења.

Један од начина да се реши овај проблем који ради добро када су комплексни записи (као што је у релационој бази података) који су сортирани према малом пољу кључа да се створи индекс у низу, а затим сортирање индекса уместо целог низа. (Сортирана верзија целог низа онда се може одједном одштампати читајући из индекса, али често ни то није неопходно, јер је индекс адекватно сортиран) Будући да је индекс много мањи од целог низа, може се лако уклопити у меморију у коју цео низ не би, ефикасно елиминише проблем са замене-диска. Овај поступак се назива "означавање".^[27]

Друга техника за превазилажење проблема меморије величине је да се комбинују два алгоритма на начин који узима предности од оба да би дошло до побољшања укупне перформансе. На пример, низ може бити подељен на делове величине који се уклапају у РАМ, садржај сваког дела се сортира коришћењем ефикасног алгоритма (као што је брзи алгоритам), а резултати се споје помоћу к-начина слично оној процедури која се користи код спајања. Ово је брже од обављања спајања или брзог сортирања за целу листу.

Технике се могу комбиновати. За сортирање веома великих скупова података који у великој мери прелазе системску меморију, чак и индекс можда треба да се сортира помоћу алгоритма или комбинације алгоритама дизајнираних да разумно наступе са виртуелном меморијом, односно да се смањи потребна количина замене.

Неефикасна сортирања

Неки алгоритми су спори у поређењу са већ горе дискутованим алгоритмима, као што је "глупо" сортирање O(н!) и "марионета" O(н^2.7).

Повезани алгоритми 

Повезани проблеми укључују и делимично сортирање (сортирање само к најмањег елемента листе, или алтернативно израчунавања к најситнијих елемената, али неуређено) и селекција (пребројавање к најмањих елемената). Ово се може неефикасно решити тоталним сортирањем, али постоје ефикаснији алгоритми, често добијени уопштавањем алгоритма за сортирање. Најзначајнији пример је брза селекција, која је сродна брзом сортирању. Насупрот томе, неки алгоритми сортирања могу да буду изведени поновном применом селекције алгоритма; брзо и брзо селективно се могу посматрати као супротни потези, јер се разликују само у томе да ли се примењује на обе стране (брзо сортирање, подели па владај) или на једну страну (брзо-селективно, смањи и владај)

Супротна врста од алгоритма за сортирање је алгоритам мешања. Ово је фундаментално другачије, јер захтевају извор случајних бројева. Занимљиво је да мешања може да спроводи алгоритам за сортирање, наиме случајним сортирањем: додељивање случајног броја сваком елементу листе а затим сортирање на основу случајних бројева. Ово се обично не спроводи у пракси, међутим и ту је познат једноставан и ефикасан алгоритам за мешање: Фишер-Јетсов мешач.

Алгоритми сортирања су такође дати за паралелне рачунаре. Ови алгоритми могу бити покренути у једном току упутства за вишеструке податке рачунара. Хаберманово комшијски паралелно сортирање^[28] сортира к елементе користећи к процесе у к корака. Овај чланак^[29] уводи оптималне алгоритме за паралелне рачунаре где се рк елементи сортирају помоћу к процеса у к корацима.

Види још

• Упоређивање
• Сортирање мрежа (упоређивањем)
• "Шварциан" трансформација
• Алгоритми претраживања
• Квантно сортирање
• Глупи сорт
• Подели па владај (информатика)

Референце

1. Demuth, H. Electronic Data Sorting.
2. Ajtai, M.; Komlós, J.; Szemerédi, E. (1983).
3. Huang, B. C.; Langston, M. A. (December 1992).
4. „SELECTION SORT (Java, C++) | Algorithms and Data Structures”. Algolist.net. Приступљено 1. 2. 2016. 
5. „Архивирана копија” (PDF). Архивирано из оригинала (PDF) 23. 08. 2022. г. Приступљено 10. 11. 2015. 
6. Kagel, Art (November 1985).
7. Franceschini, G. (June 2007).
8. Kim, P. S.; Kutzner, A. (2008).
9. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd изд.), MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3 .
10. Goodrich, Michael T.; Tamassia, Roberto. „4.5 Bucket-Sort and Radix-Sort”. Algorithm Design Foundations, Michael T. Goodrich & Roberto. 
11. Han, Y. (January 2004).
12. Thorup, M. (February 2002).
13. Yijie Han; Thorup, M. (2002).
14. Wirth 1986, стр. 76–77.
15. Wirth 1986, стр. 79–80.
16. Wirth 1986, стр. 101–102.
17. „Tim Peters's original description of timsort”. Архивирано из оригинала 22. 01. 2018. г. Приступљено 1. 2. 2016. 
18. „OpenJDK's TimSort.java”. Архивирано из оригинала 14. 08. 2011. г. Приступљено 1. 2. 2016. 
19. details, Contact. „Perl sort documentation”. Perldoc.perl.org. Приступљено 1. 2. 2016. 
20. Merge sort in Java 1.3 Архивирано на сајту Wayback Machine (4. март 2009), Sun.
21. Java 1.3 live since 2000
22. Wirth 1986, стр. 87–89.
23. Wirth 1986, стр. 93.
24. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), Introduction to Algorithms (3rd ed.
25. Wirth 1986, стр. 81–82.
26. Brejová, B. (15 September 2001).
27. PCMag.com (28. 1. 2016). „Definition of "tag sort" according to PC Magazine”. Pcmag.com. Архивирано из оригинала 06. 10. 2012. г. Приступљено 1. 2. 2016. 
28. „Carnegie Mellon University data repository”. Архивирано из оригинала 06. 10. 2015. г. Приступљено 10. 11. 2015. 
29. „Carnegie Mellon University data repository”. Архивирано из оригинала 06. 10. 2015. г. Приступљено 10. 11. 2015. 

Литература

• Goodrich, Michael T.; Tamassia, Roberto. „4.5 Bucket-Sort and Radix-Sort”. Algorithm Design Foundations, Michael T. Goodrich & Roberto. 
• Wirth, Niklaus (1986). Algorithms & Data Structures. Upper Saddle River, NJ: Prentice-Hall. ISBN 978-0-13-022005-9. 
• Knuth, Donald E. (1998). Sorting and Searching. The Art of Computer Programming. 3 (2nd изд.). Boston: Addison-Wesley. ISBN 978-0-201-89685-5. 
• Knuth, D. E. The Art of Computer Programming Volume 3: Sorting and Searching (3rd изд.). Addison-Wesley Professional. ISBN 978-0-201-48541-7. 
• Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (1992). Numerical Recipes in C: The Art of Scientific Computing (Second изд.). Cambridge University Press. ISBN 978-0-521-43108-8. 
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (Third изд.). The MIT Press. ISBN 978-0-262-03384-8. 

Спољашње везе

• Sorting Algorithm Animations - Графичка илустрација како различити алгоритми користе различите врсте сетова података.
• Sequential and parallel sorting algorithms Архивирано на сајту Wayback Machine (13. децембар 2012) - Објашњења и анализе многих алгоритама за сортирање.
• Dictionary of Algorithms, Data Structures, and Problems - Речник алгоритама, техника, заједничких функција, и проблема.
• Slightly Skeptical View on Sorting Algorithms Разматра неколико класичних алгоритама и промовише алтернативе "брзо сортирајућег" алгоритма.
• 15 Sorting Algorithms in 6 Minutes (Youtube) Визуелизација и "аудизација" 15 алгоритама сортирања за 6 минута.
• A036604 sequence in OEIS database titled "Sorting numbers: minimal number of comparisons needed to sort n elements" који обављају Форд-Џонсонови алгоритми.
• Методе сортирања низова
• Поређење алгоритама сортирања