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