Sąlajos rikiavimo algoritmas
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Algoritmas | |
Tipas | Rikiavimo algoritmai |
Pavadinimas | Sąlajos (Merge sort) |
Sudėtingumas | Vidutinis - N·log(N)); blogiausias - N·log(N) |
Greitos nuorodos |
|
Sąlajos rikiavimas (angl. mergesort) - vienas iš "skaldyk ir valdyk" paradigma besiremiančių rikiavimo algoritmų. Jo principas - skaidyti duomenis į dvi dalis, kiekvieną dalį atskirai surikiuota ir po to sulieti, taikant šį principą rekursyviai. Šio algoritmo realizacijos dažniausiai naudoja pagalbinę atmintį.
Algoritmo efektyvumas nepriklauso nuo duomenų, stabilus, sudėtingumas - O(N·logN), papildomos atminties tūris proporcingas duomenų kiekiui. Galima algoritmą derinti su kitais rikiavimo algoritmais, taip pagerinant efektyvumą.