Positsioonimeetod

Positsioonimeetod (inglise radix sort) on arvutiteaduses mittevõrdlev sortimisalgoritm. See meetod väldib võrdlemist, luues kimbud ja jaotades elemendid kimpudesse vastavalt nendest järjest võetud järgule. Rohkem kui ühe numbriga elementide puhul korratakse seda lahtrisse paigutamise protsessi iga järgu jaoks, säilitades samal ajal eelmise etapi järjestus, kuni kõik järgud on arvesse võetud. Sel põhjusel on positsioonimeetodiga sorteerimist kutsutud ka kimbumeetodiks ja digitaalseks sorteerimiseks.

Positsioonimeetodit saab rakendada andmetele, mida saab leksikograafiliselt sorteerida, olgu need siis täisarvud, sõnad, perfokaardid, mängukaardid või kirjad.

 Algoritm (arvude korral) 
 Arvud jagatakse 10 ossa vastavalt üheliste järgus olevale väärtusele.
 Osad tõstetakse järjekorras kokku. 
 Arvud jaotatakse 10 ossa kümneliste väärtuse järgi.
 Osad tõstetakse järjekorras kokku. 
 Sama korratakse sajaliste, tuhandeliste jne puhul. Kui arvud on üheliste järgi ära jagatud, peavad kümneliste järgi tekkivates hunnikutes ühelised omavahelise järjekorra säilitama.
+AlgseisÜhelisedKümnelisedSajalised123 
880 

276 

147 

282 

562880 
282 

562 

123 

276 

147123 
147  

562 

276  

282 

880123 
147 

276 

282 

562 

880

 Keerukus 
Algoritmi ajaline keerukus sõltub sellest, millist algoritmi ühe järgu järgi järjestamiseks kasutada. Arvudest järkude kättesaamiseks tuleb uurida konkreetse keele võimalusi. Ajalise keerukuse osas on saavutatav .

 Ajalugu 
Meetod pärineb ajast, kui andmeid hoiti perfokaartidel ja neid oli vaja mingil alusel järjestada. Järjestamistöö tegi spetsiaalne masin. Kõigepealt järjestati kaardid ringi kõige "noorema" veeru järgi: vastavalt tulbas perforeeritud väärtusele 0–9 moodustati 10 hunnikut ja seejärel tõsteti hunnikud uuesti üksteise peale üheks hunnikuks. Järgmisel sammul tehti sama eelviimase tulbaga jne kuni kõigi tulpade järgi oli kogu hunnik korra ringi tõstetud. Nii saab kogu pakk sorteeritud. Oluline on, et kaartide järjekorda pärast hunnikutesse tõstmist hunniku sees muuta ei tohi. Kirjalikul kujul on vastavalt D. Knuthile see algoritm selgitatud 1929. aastal sorteerimismasina juhendis, autoriks L. J. Comrie. Asendades perfokaardid arvudega, saame sorteerida sama kohtade arvuga arve (kolmekohalisi, neljakohalisi jne).

 Viited 

Kategooria:Sortimisalgoritmid