Tuvipesa meetod

+Tuvipesa meetodKlassSortimisalgoritmAndmestruktuurJärjend (Inglise Array)Halvim juht, kus N on võtmeväärtuste vahemik ja n on sisendsuurusOptimaalne juhtAinult kui 
Tuvipesa meetod (inglise Pigeonhole Sort) on sortimisalgoritm, mis sobib elementide loendite sortimiseks, kus elementide arv  ja võimalike võtmeväärtuste vahemiku pikkus  on ligikaudu samad.  Selle ajaline keerukus on . 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:

 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.
 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.
 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  on palju suurem kui , on kimbumeetod  ruumis ja ajas tõhusam.

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

 Viited 

Kategooria:Sortimisalgoritmid