Mine sisu juurde

Positsioonimeetod

Allikas: Vikipeedia

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)

[muuda | muuda lähteteksti]

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

[2]

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]

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]

  1. "US 395781". Espacenet. Originaali arhiivikoopia seisuga 22. oktoober 2022. Vaadatud 9. detsembril 2024.
  2. 2,0 2,1 2,2 Inga, Petuhhov. "Tutvustame mõningaid sorteerimisalgoritme" (PDF). TLÜ. Lk 12. Vaadatud 09.12.2024.