Back

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




                                     

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

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

                                     

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

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

                                     

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

Иако је принцип концептуално једноставан, праволинијска имплементација би била доста тешка због тога што овим процесом настаје све већи број све мањих група о којима треба водити евиденцију, што се не може урадити на неки посебно ефикасан начин. Према томе, треба задржати једноставност основне идеје, а поступак модификовати тако да и имплементација буде ефикасна. Ефикасна мплементација се може постићи ако се започне тако што се у првом кораку врши сортирање по најмлађој цифри. Узимају се редом елементи из неуређеног низа и разврставају се у десет редова Q 0 … {\displaystyle \dots } Q 9 по вредности најмлађе цифрре, тако што се текући елемент ставља на крај одговарајућег реда. Кад се тако обраде сви елементи, онда се сви редови опет споје у један низ по поретку Q 0 … {\displaystyle \dots } Q 9. У следећем кораку се опет узимају елементи овог низа редом и разврставају у редове, али по вредности друге цифре d 1, па се опет на крају сви редови споје. Поступак се завршава кад се изврши уређење и по најстаријој цифри d k-1.

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

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

                                     

3. Примери

Први пример

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

191 222 213 214

Други корак:

213 214 222 191

Трећи корак:

191 213 214 222

Други пример

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

72 0 35 5 43 6 45 7 65 7 32 9 83 9

Други корак:

7 2 0 3 2 9 4 3 6 8 3 9 3 5 4 5 7 6 5 7

Коначно:

329 355 436 457 657 720 839
                                     

4. Перформансе

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

Ако k није константа већ расте са n, онда се повећава и временска сложеност. На пример, ако су кључеви густи, па скуп кључева покрива скоро читав скуп могућих вредности, онда се k приближава l o g n {\displaystyle logn}, а сложеност се приближава O n l o g n {\displaystyle Onlogn}.



                                     

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

  • USort library Архивирано на сајту Wayback Machine 7. август 2011 садржи имплементације радикс сорта за већину нумеричких C типоваC99
  • Чланак о Радикс сортирању IEEE 754 бројева са покретним зарезом, уз имплементацију. Брже сортирање са покретним зарезом уз имплементацију у C++
  • Open Data Structures - C++ Edition - Section 11.2 - Counting Sort and Radix Sort
  • Open Data Structures - Java Edition - Section 11.2 - Counting Sort and Radix Sort
  • BRADSORT v1.50 изворни код
  • Демонстрација и поређење Радикс сорта са Bubble sort, Merge sort and Quicksort имплементирано у Јаваскрипт

Users also searched:

...