A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Triedenie zlučovaním (merge sort) je triediaci algoritmus, netriedi na mieste.
Tento algoritmus triedenia mal veľký význam v minulosti pri triedení údajov na magnetických páskach (médium so sekvenčným prístupom), keďže vyžaduje len malé množstvo pamäte s priamym prístupom.
Asymptotická zložitosť pre priemerný aj najhorší prípad je .
Algoritmus
Merge sort principiálne funguje v 3 krokoch:
- rozdelenie zoznamu na 2 časti
- zoradenie každej časti zvlášť
- zlúčenie oboch častí
Jeho jednoduchý zápis by vyzeral asi takto:
function mergesort(m) var list left, right if length(m) ≤ 1 return m else middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after middle add x to right left = mergesort(left) right = mergesort(right) result = merge(left, right) return result end if
Funkcionálny zápis tohto algoritmu vyzerá nasledovne:
mergeSort :: Ord a ⇒ → mergeSort = mergeSort = mergeSort s = merge (mergeSort u) (mergeSort v) where (u,v) = splitAt (n `div` 2) s n = length s merge :: Ord a ⇒ → → merge s = s merge t = t merge (x:u) (y:v) = if x ≤ y then x : merge u (y:v) else y : merge (x:u) v
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antropológia
Aplikované vedy
Bibliometria
Dejiny vedy
Encyklopédie
Filozofia vedy
Forenzné vedy
Humanitné vedy
Knižničná veda
Kryogenika
Kryptológia
Kulturológia
Literárna veda
Medzidisciplinárne oblasti
Metódy kvantitatívnej analýzy
Metavedy
Metodika
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk