Tuvipesa meetod

Tuvipesa meetod

Klass	Sortimisalgoritm
Andmestruktuur	Järjend (Inglise Array)
Halvim juht	$O(N+n)$, kus N on võtmeväärtuste vahemik ja n on sisendsuurus
Optimaalne juht	Ainult kui $N=O(n)$

Tuvipesa meetod (inglise Pigeonhole Sort) on sortimisalgoritm, mis sobib elementide loendite sortimiseks, kus elementide arv $n$ ja võimalike võtmeväärtuste vahemiku pikkus $N$ on ligikaudu samad. Selle ajaline keerukus on $O(n+N)$. See sarnaneb loendamismeetodi (Inglise counting sort), kuid erineb selle poolest, et see "teisaldab elemente kaks korda: üks kord kimpudesse kimbumeetodi kohaselt ja uuesti lõppsihtkohta, kus aga loendamismeetod loob abimassiivi, seejärel kasutab algset massiivi iga elemendi lõppsihtkoha arvutamiseks ja teisaldab elemendi sinna."

Tuvipesa meetod töötab järgmiselt:

1. Arvestades sorteeritavate väärtuste massiivi, tuleb luua algselt tühjade "tuvipesade" paisktabel, kus on üks tuvipesa iga võtme jaoks algse massiivi võtmete vahemikus.
2. Algset massiivi läbi käies tuleb asetada iga väärtus vastava võtmega paisktabelis asuvasse tuvipessa, nii et iga tuvipesa sisaldab lõpuks kõigi selle võtmega väärtuste loendit.
3. Massiiv tuleb läbi käia kasvavas järjekorras ja lisada kõik elemendid algsesse massiivi, mis on nüüd sorteeritud.

Näide

Oletame, et sorteeritakse antud väärtuste paare nende esimese elemendi järgi:

• (5, "tere")
• (3, "pirukas")
• (8, "õun")
• (5, "kuningas")

Iga väärtuse jaoks vahemikus 3 kuni 8 loome tuvi pesa, seejärel liigutame iga elemendi oma pessa:

• 3: (3, "pirukas")
• 4:
• 5: (5, "tere"), (5, "kuningas")
• 6:
• 7:
• 8: (8, "õun")

Seejärel itereeritakse massiivi järjest ja elemendid viiakse tagasi algsesse tulemuse loendisse.

Tuvipesa meetodi ja loendamismeetodi erinevus seisneb selles, et loendamismeetodi korral ei sisalda abimassiivi sisendelementide loendeid, vaid loeb:

• 3:1
• 4:0
• 5:2
• 6:0
• 7:0
• 8:1

Massiivide puhul, kus $N$ on palju suurem kui $n$, on kimbumeetod ruumis ja ajas tõhusam.

Vaata ka

• Tuvipesa põhimõte
• Positsioonimeetod
• Kimbu järjekord, sellega seotud prioriteetse järjekorra andmestruktuur