Kimbumeetod

Kimbumeetod (inglise Bucket sort) on sorteerimisalgoritm, mis töötab, jaotades massiivi elemendid mitmesse kimpu (teatud ka kui ämbrisse). Iga kimp sorteeritakse seejärel eraldi, kas kasutades erinevat sorteerimisalgoritmi või rakendades kimbumeetodit rekursiivselt. See on jaotussordi, üldistus tuvipesa meetodist (Inglise pigeonhole sort), mis võimaldab jaotada mitu võtit ühte kimpu, ja on positsioonimeetodi (inglise radix sort) sugulane, kus sorteerimine toimub kõige olulisemast numbrist vähem olulisemani. Kimbumeetodit saab rakendada võrdlustega ja seetõttu võib seda pidada ka võrdlussorteerimisalgoritmiks. Arvutuslik keerukus sõltub iga kimbu sorteerimiseks kasutatavast algoritmist, kimpude arvust ja sellest, kas sisend on ühtlaselt jaotatud.

Näide

Kimbumeetod töötab järgmiselt:

1. Loo algselt tühjade “kimpude” massiiv.

2. Jaota: Käi läbi algne massiiv, pannes iga objekti oma kimpu.

3. Sorteeri iga mitte-tühi kimp.

4. Kogu: Käi järjest kimpe läbi ja pane kõik elemendid tagasi algsesse massiivi.