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

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

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

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

Основна идеја

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

Имплементација

Иако је принцип концептуално једноставан, праволинијска имплементација би била доста тешка због тога што овим процесом настаје све већи број све мањих група о којима треба водити евиденцију, што се не може урадити на неки посебно ефикасан начин. Према томе, треба задржати једноставност основне идеје, а поступак модификовати тако да и имплементација буде ефикасна. Ефикасна имплементација се може постићи ако се започне тако што се у првом кораку врши сортирање по најмлађој цифри. Узимају се редом елементи из неуређеног низа и разврставају се у десет редова Q₀ $\dots$ Q₉ по вредности најмлађе цифре, тако што се текући елемент ставља на крај одговарајућег реда. Кад се тако обраде сви елементи, онда се сви редови опет споје у један низ по поретку Q₀ $\dots$ Q₉. У следећем кораку се опет узимају елементи овог низа редом и разврставају у редове, али по вредности друге цифре d₁, па се опет на крају сви редови споје. Поступак се завршава кад се изврши уређење и по најстаријој цифри d_k-1.

Суштина овог алгоритма је у стабилности процеса сортирања, која је омогућена убацивањем елемената у ред на његов крај. Према томе, када се у i-том кораку врши сортирање по цифри d_i-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 приближава $logn$, а сложеност се приближава $O(nlogn)$.

Погледајте

• Алгоритми сортирања[1]

Литература

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

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

• Демонстрација и поређење Радикс сорта са Bubble sort, Merge sort and Quicksort имплементирано у Јаваскрипт
• Чланак о Радикс сортирању IEEE 754 бројева са покретним зарезом, уз имплементацију.

  Брже сортирање са покретним зарезом уз имплементацију у C++

• USort library Архивирано на сајту Wayback Machine (7. август 2011) садржи имплементације радикс сорта за већину нумеричких C типова(C99)
• BRADSORT v1.50 изворни код
• Open Data Structures - Java Edition - Section 11.2 - Counting Sort and Radix Sort
• Open Data Structures - C++ Edition - Section 11.2 - Counting Sort and Radix Sort