Positsioonimeetod
Mall:Toimeta Arvutiteaduses on positsioonimeetod (inglise radix sort) 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 positioonimeetodiga sorteerimist kutsutud ka kimbumeetodiks ja digitaalseks sorteerimiseks.
Posaitsioonimeetodit saab rakendada andmetele, mida saab leksikograafiliselt sorteerida, olgu need siis täisarvud, sõnad, perfokaardid, mängukaardid või kirjad.[1]
Algoritm (Arvude korral)
1. Arvud jagatakse 10sse 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 kordub sajaliste, tuhandeliste jne kohta. 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 .[2]
Ajalugu
Meetod pärineb ajast, kui andmete hoidmiseks kasutati perfokaarte ja neid oli vaja mingil alusel järjestada. Järjestamistööd tegi edukalt spetsiaalne masin. Kõigepealt järjestati kaardid ringi kõige "noorema" veeru järgi - vastavalt tulbas perforeeritud väärtusele 0 .. 9 moodustati 10 erinevat 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. Selliselt saab kogu pakk sorteeritud. Oluline on, et kaartide järjekorda peale hunnikutesse tõstmist hunniku sees muuta ei tohi. Kirjalikul kujul on vastavalt D. Knuthile see algoritm selgitatud 1929. a. sorteerimismasina juhendis, autoriks L. J. Comrie. Asendades perfokaardid arvudega saame sorteerida sama kohtade arvuga arve (3-kohalisi, 4-kohalisi jne).[2]