"rekursioonist" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

11.3 Mestimisega sorteerimine (Merge s.) • Algoritm koosneb kahest osast – massiivi jagamisest ning kahe osa ühendamisest. 1. Jaga algandmed kaheks enam vähem võrdseks osaks. 2. Sorteeri kumbki osa eraldi. 3. Kombineeri mõlemad osad kokku üheks sorteeritud massiiviks. • Olemuselt on see algortim rekursiivne ja toetub otseselt lähenemisele "Jaga ja valitse” (divide et impera). Rekursioonist väljudes ühendatakse massiivi osi järjest omavahel, saades nii üha pikemad sorteeritud lõigud. Vajab täiendavat mälu ajutiste massiivide tegemiseks (reaalselt sama palju kui on sorteeritavaid andmeid) • Keerukus: O(n log2n) nii halvimal kui ka keskmisel juhul. 11.3.1 Tugevad küljed • Stabiilne • Toimib hästi koos virtuaalse ja cache mäluga • Saab tööd jagada protsessorite vahel • Ei oma “raskeid” sisendandmeid