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

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

Имплементација 
Иако је принцип концептуално једноставан, праволинијска имплементација би била доста тешка због тога што овим процесом настаје све већи број све мањих група о којима треба водити евиденцију, што се не може урадити на неки посебно ефикасан начин. Према томе, треба задржати једноставност основне идеје, а поступак модификовати тако да и имплементација буде ефикасна. Ефикасна мплементација се може постићи ако се започне тако што се у првом кораку врши сортирање по најмлађој цифри. Узимају се редом елементи из неуређеног низа и разврставају се у десет редова Q0  Q9 по вредности најмлађе цифрре, тако што се текући елемент ставља на крај одговарајућег реда. Кад се тако обраде сви елементи, онда се сви редови опет споје у један низ по поретку Q0  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 корака обрађују сви елементи, временска сложеност је реда . Ако је број цифара k константан, онда је сложеност линеарна. Због линеарне сложености ово је врло ефикасан метод за кратке кључеве. Уколико су кључеви дугачки, перформанса опада, па се тада најчешће користи усвојити неко хибридно решење. Принцип радикс сортирања се може применити само на мањи број најстаријих цифара, што даје непотпуно сортираран низ, али донекле уређен. Завршно сортирање се тада обавља неким методом који је ефикасан за прилично уређене низове, као што је директно уметање.

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

Погледајте 
 Алгоритми сортирања

Литература 
 .

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

 Демонстрација и поређење Радикс сорта са Bubble sort, Merge sort and Quicksort имплементирано у Јаваскрипт
 Чланак о Радикс сортирању IEEE 754 бројева са покретним зарезом, уз имплементацију.
 Брже сортирање са покретним зарезом уз имплементацију у C++
 USort library  садржи имплементације радикс сорта за већину нумеричких 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

Алгоритми сортирања
Стабилно сортирање
Радикс сорт ( ) је алгоритам сортирања који користи позициону репрезентацију и одвојено анализира цифре ( или знакове ) на различитим позицијама . За демонстрацију идеје алгоритма , без губитка општости , претпоставља се да су кључеви децимални бројеви са истим бројем од k цифара dk-1 dk-2 \ .. d0. Основна идеја Оснобна идеја је раздвајање бројева угрупа на основу вредности прве , најстарије цифре dk-1 . Тиме се изврши грубо сортирање јер је сваки број из групе која одговара мањој првој цифри мањи од бројева из група које одговарају већој првој цифри . Затим се изврши сортирање у оквиру сваке групе на поподгрупа у зависности од вредности друге цифре dk-2. Поступак се рекурзивно наставља и завршава у k корака , при чему је последњи корак сортирање по најмлађој цифри d0 , после чега је улазни низ сортиран . Имплементација Иако је принцип концептуално једноставан , праволинијска имплементација би била доста тешка због тога што овим процесом настаје све већи број све мањих група о којима треба водити евиденцију , што се не може урадити на неки посебно ефикасан начин . Према томе , треба задржати једноставност основне идеје , а поступак модификовати тако да и имплементација буде ефикасна . Ефикасна мплементација се може постићи ако се започне тако што се у првом кораку врши сортирање по најмлађој цифри . Узимају се редом елементи из неуређеног низа и разврставају се у десет редова Q0 Q9 по вредности најмлађе цифрре , тако што се текући елемент ставља на крај одговарајућег реда . Кад се тако обраде сви елементи , онда се сви редови опет споје у један низ по поретку Q0 Q9. У следећем кораку се опет узимају елементи овог низа редом и разврставају у редове , али по вредности друге цифре d1 , па се опет на крају сви редови споје . Поступак се завршава кад се изврши уређење и по најстаријој цифри dk-1 . Суштина овог алгоритма је у стабилности процеса сортирања , која је омогућена убацивањем елемената у ред на његов крај . Према томе , када се у i-том кораку врши сортирање по цифри di-1 , већи је онај елемент који има вишу цифру на тој позицији и он иде у одговарајући ред . Елементи са истом цифром иду у исти ред , али су они због стабилности метода већ уређени по нижим цифрама . Ово омогућава спајање редова без вођења рачуна о њиховим границама . Приликом имплементације алгоритма треба водити рачуна о томе да се број елемената у редовима у појединим корацима не може предвидети . Зато секвенцијална реализација редова није погодна , већ се прибегава уланчаној репрезентацији . Редови се одржавају као уланчане листе у које се нови елементи стављају на крај . Због тога је за сваки ред потребно обезбедити показиваче који показују на почетак и крај листе . На почетку се од неуређеног низа направи једна листа из које се узимају елементи и стављају у редове . После сваког корака све листе се опет надовезују у једну листу , почевши од листе која одговара цифридо цифре која одговара цифри Примери Први пример Узмимо за пример да треба да сортирамо низ191214 користећи радикс сорт . Први корак : 222214 Други корак : 214191 Трећи корак : 213222 Други пример Сортирамо радикс сортом троцифрене бројеве Први корак : Други корак : Коначно : Перформансе Временска сложеност метода зависи од броја цифара k и од броја елемената n . Како се у сваком од k корака обрађују сви елементи , временска сложеност је реда \ . Ако је број цифара k константан , онда је сложеност линеарна . Због линеарне сложености ово је врло ефикасан метод за кратке кључеве . Уколико су кључеви дугачки , перформанса опада , па се тада најчешће користи усвојити неко хибридно решење . Принцип радикс сортирања се може применити само на мањи број најстаријих цифара , што даје непотпуно сортираран низ , али донекле уређен . Завршно сортирање се тада обавља неким методом који је ефикасан за прилично уређене низове , као што је директно уметање . Ако k није константа већ расте са n , онда се повећава и временска сложеност . На пример , ако су кључеви густи , па скуп кључева покрива скоро читав скуп могућих вредности , онда се k приближава , а сложеност се приближава \ . Погледајте Алгоритми сортирања Литература \ . Спољашње везе Демонстрација и поређење Радикс сорта са Bubble sort , Merge sort and Quicksort имплементирано у Јаваскрипт Чланак о Радикс сортирању IEEEбројева са покретним зарезом , уз имплементацију . Брже сортирање са покретним зарезом уз имплементацију у C++ USort library садржи имплементације радикс сорта за већину нумеричких C типова( C99 ) BRADSORT v1.50 изворни код Open Data Structures - Java Edition - Section2 - Counting Sort and Radix Sort Open Data Structures - C++ Edition - Section2 - Counting Sort and Radix Sort Алгоритми сортирања Стабилно сортирање