Back

ⓘ Сортирање поређењем




Сортирање поређењем
                                     

ⓘ Сортирање поређењем

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

  • за свако a и b, или a ≤ b или b ≤ a трихотомија.
  • ако a ≤ b и b ≤ c онда a ≤ c транзитивност

Ако је могуће да a ≤ b и b ≤ a ; у овом случају један или други могу доћи први у сортирану листу. У, у овом случају улазни редослед одређује сортирани редослед.

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

                                     

1. Примери

Неки од најпознатијих алгоритама поређења укључују:

  • Интро сорт
  • Сортирање уметањем
  • Сортирање спајањем
  • Квиксорт
  • Пар-непар сортирање
  • Хипсорт
  • Коктел сортирање
  • Сортирање мехуром
  • Циклично сортирање
  • Сортирање селекцијом
  • Смутсорт
  • Тимсорт
                                     

2. Ограничења перформанси и предности различитих техника сортирања

Постоје основна ограничења за перформансе сортирања поређењем. Сортирање поређењем мора да има просечну доњу границу Ωn log n операција поређења, што је познато и као линеаритмичко време. Ово је последица ограничења информација доступних кроз сама поређења - или, да га стави другачије, у неодређене алгебарске структуре потпуно уређених скупова. У овом смислу, сортирање спајањем, хипсорт, и интросорт су асимптотички оптимални у смислу броја поређења које морају да одраде, иако ово метрички занемарује друге операције. Сортирања која немају поређења као што су пример испод могу да достигну On перформансу коришћењем других операција, допуштајући им да заобиђу ову доњу границу под претпоставком да су елементи константне величине.

Приметите да сортирање поређењем може бите брже на неким листама; много адаптивних сортирања као што је сортирање уметањем ради у On времену на већ сортираној или полу-сортираној листи. Ωn log n доња граница прихвата само случајеве у којима улазна листа може бити у било ком могућем редоследу.

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

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

function NtorkaPoredjenje) if leviA ≠ desniA return compareleviA, desniA else if leviB ≠ desniB return compareleviB, desniB else return compareleviC, desniC

Балансирана тернарна нотација омогућава да поређење буде у једном кораку, а резултати буду "мање", "веће" или "једнако".

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

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

                                     

3. Алтернативе

Неки проблеми сортирања захтевају искључиво брже решење него Ωn log n граница за Сортирање поређењем; пример је целобројно сортирање, где су сви кључеви цели бројеви. Када кључеви чине мали распон, Сортирање пребројавањем је пример алгоритма који ради у ленеарном времену. Остали целобројни алгоритми сортирања, као што је радикс сортирање, нису асимптотички бржи од сортирања поређењем, али у пракси могу бити бржи.

Проблем сортирања парова по њиховом збиру не подлеже Ωn ² log n граници или квадрату резултата упаривања; најбољи познати алгоритам и даље има On ² log n временску сложеност, али само On ² поређења.

                                     

4. Број проређења неопходних за сортирање листе

Број поређења који овај алгоритам захтева повећање у пропорцији са n log ⁡ n {\displaystyle n\logn}, где n {\displaystyle n} је број елемената за сортирање. Ова граница је асимптотички мала.

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

2 f n ≥ n! {\displaystyle 2^{fn}\geq n!}, или еквивалентно f n ≥ log 2 ⁡ n!. {\displaystyle fn\geq \log _{2}n!.}

Из Стирлингове апроксимације знамо да log 2 ⁡ n! {\displaystyle \log _{2}n!} је Ω n log 2 ⁡ n {\displaystyle \Omega n\log _{2}n}. Ово потврђује тврдњу за доњу границу.

Идентична горња граница следи из алгоритама који достиже ову границу у најгорем случају.

Наведени аргумент омогућује апсолутну, а не само асимптотичку доњу границу броја поређења, тј. ⌈ log 2 ⁡ n! ⌉ {\displaystyle \lceil \log _{2}n!\rceil } поређења. Ова доња граница је стварно добра може се постићи са простим алгоритмом сортирања спајањем, али је познат да може бити нетачан. На пример, ⌈ log 2 ⁡ 13! ⌉ = 33 {\displaystyle \lceil \log _{2}13!\rceil =33}, али најмањи број поређења за 13 елемената је 34 што је доказано.

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



                                     

4.1. Број проређења неопходних за сортирање листе Доња граница за просечан број поређења

Слична граница важи и за просечан броја поређења. Под претпоставком да

  • су сви кључеви различити, нпр. свако поређење ће дати или a> b или a
                                     
  • обзира да ли је то сортирање поређењем или не. Сортирање поређењем испитује податке само поређењем два елемента са оператором поређења Општи метод: уметање
  • Библиотечко сортирање је алгоритам сортирања базиран на сортирању уметањем, који користи размаке унутар низа како би убрзао узастопна уметања. Овај алгоритам
  • Sortiranje mehurom ili Bablsort engl. Bubble sort ponekad pogrešno nazvano potapajuće sortiranje algoritam je koji se koristi za sortiranje nizova
  • Sortiranje spajanjem енгл. merge sort je algoritam sortiranja baziran na poredenju složenosti O n log n Većina implementacija daje stabilan niz, što
  • Сортирање каскадним спајањем је слично сортирању полифазним спајањем али користи једноставнију дистрибуцију. Спајање је спорије него полифазно спајање
  • do najmanje težine. Kofa sortiranje je generalizaciija pretinac sortiranja.Pošto kofa sortiranje nije sortiranje poredenjem donja granica Ω n log n
  • broj obilazaka se neće znati dok fajl ne bude pročitan Za poredenje obično merge sortiranje će kombinovati 16 obilazaka u 4 iteracije koristeći 4 fajla
  • algoritam za sortiranje u mestu zasnovan na poredenju elemenata. Ovo je generalizacija sortiranja kod kojih elementi menjaju mesta, kao što su Sortiranje umetanjem
  • Палачинка сортирање је варијација алгоритма сортирања у коме је једина дозвољена операција обртање елемената префикса у секвенци. За разлику од традиционалних
  • Sortiranje umetanjem engl. Insertion sort je jednostavan algoritam za sortiranje koji gradi završni sortirani niz jednu po jednu stavku. Mnogo je manje