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)

1. Arvud jagatakse 10 ossa vastavalt üheliste järgus olevale väärtusele.
2. Osad tõstetakse järjekorras kokku.
3. Arvud jaotatakse 10 ossa kümneliste väärtuse järgi.
4. Osad tõstetakse järjekorras kokku.
5. 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	Ühelised	Kümnelised	Sajalised
123 880 276 147 282 562	880 282 562 123 276 147	123 147 562 276 282 880	123 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 $O(n)$.

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).