Радикс сортирање

Из Википедије, слободне енциклопедије
Радикс сортирање
Намена сортирање
Структура података низ
Временска компл. O(kn) до O(n logn)

Радикс сорт (енгл. Radix sort) је алгоритам сортирања који користи позициону репрезентацију и одвојено анализира цифре (или знакове) на различитим позицијама. За демонстрацију идеје алгоритма, без губитка општости, претпоставља се да су кључеви децимални бројеви са истим бројем од k цифара dk-1 dk-2 .. d0.

Основна идеја[уреди]

Оснобна идеја је раздвајање бројева у 10 група на основу вредности прве, најстарије цифре dk-1. Тиме се изврши грубо сортирање јер је сваки број из групе која одговара мањој првој цифри мањи од бројева из група које одговарају већој првој цифри. Затим се изврши сортирање у оквиру сваке групе на по 10 подгрупа у зависности од вредности друге цифре dk-2. Поступак се рекурзивно наставља и завршава у k корака, при чему је последњи корак сортирање по најмлађој цифри d0, после чега је улазни низ сортиран.

Имплементација[уреди]

Иако је принцип концептуално једноставан, праволинијска имплементација би била доста тешка због тога што овим процесом настаје све већи број све мањих група о којима треба водити евиденцију, што се не може урадити на неки посебно ефикасан начин. Према томе, треба задржати једноставност основне идеје, а поступак модификовати тако да и имплементација буде ефикасна. Ефикасна мплементација се може постићи ако се започне тако што се у првом кораку врши сортирање по најмлађој цифри. Узимају се редом елементи из неуређеног низа и разврставају се у десет редова Q0 \dots Q9 по вредности најмлађе цифрре, тако што се текући елемент ставља на крај одговарајућег реда. Кад се тако обраде сви елементи, онда се сви редови опет споје у један низ по поретку Q0 \dots Q9. У следећем кораку се опет узимају елементи овог низа редом и разврставају у редове, али по вредности друге цифре d1, па се опет на крају сви редови споје. Поступак се завршава кад се изврши уређење и по најстаријој цифри dk-1.

Суштина овог алгоритма је у стабилности процеса сортирања, која је омогућена убацивањем елемената у ред на његов крај. Према томе, када се у i-том кораку врши сортирање по цифри di-1, већи је онај елемент који има вишу цифру на тој позицији и он иде у одговарајући ред. Елементи са истом цифром иду у исти ред, али су они због стабилности метода већ уређени по нижим цифрама. Ово омогућава спајање редова без вођења рачуна о њиховим границама.

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

Примери[уреди]

Први пример[уреди]

Узмимо за пример да треба да сортирамо низ 213 191 222 214 користећи радикс сорт. Први корак:

191 222 213 214

Други корак:

213 214 222 191

Трећи корак:

191 213 214 222

Други пример[уреди]

Сортирамо радикс сортом троцифрене бројеве 329, 457, 657, 839, 436, 720, 355. Први корак:

720
355 
436
457
657 
329
839 

Други корак:

720 
329 
436 
839 
355 
457 
657

Коначно:

329 
355 
436 
457 
657 
720 
839

Перформансе[уреди]

Временска сложеност метода зависи од броја цифара k и од броја елемената n. Како се у сваком од k корака обрађују сви елементи, временска сложеност је реда O(kn). Ако је број цифара k константан, онда је сложеност линеарна. Због линеарне сложености ово је врло ефикасан метод за кратке кључеве. Уколико су кључеви дугачки, перформанса опада, па се тада најчешће користи усвојити неко хибридно решење. Принцип радикс сортирања се може применити само на мањи број најстаријих цифара, што даје непотпуно сортираран низ, али донекле уређен. Завршно сортирање се тада обавља неким методом који је ефикасан за прилично уређене низове, као што је директно уметање.

Ако k није константа већ расте са n, онда се повећава и временска сложеност. На пример, ако су кључеви густи, па скуп кључева покрива скоро читав скуп могућих вредности, онда се k приближава log n, а сложеност се приближава O(n log n).

Погледајте[уреди]

Спољашње везе[уреди]

Викикњиге
Викикњиге имају више информација о:

Литература[уреди]

  • Томашевић, Мило (2000), Алгоритми и структуре података, Београд: Академска мисао .