Urejanje z zlivanjem: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
+ktgr |
dodal angleški izraz in iznajditelja |
||
Vrstica 1: | Vrstica 1: | ||
⚫ | |||
[[Slika:Merge_sort_animation.gif|thumb|300px|Grafični prikaz urejanja z zlivanjem]] |
[[Slika:Merge_sort_animation.gif|thumb|300px|Grafični prikaz urejanja z zlivanjem]] |
||
[[Slika:Merge_sort_algorithm_diagram.svg.png|thumb|300px|Potek urejanja sedmih števil s rekurzivno implementacijo urejanja z zlivanjem]] |
[[Slika:Merge_sort_algorithm_diagram.svg.png|thumb|300px|Potek urejanja sedmih števil s rekurzivno implementacijo urejanja z zlivanjem]] |
||
⚫ | |||
== Delovanje == |
== Delovanje == |
Redakcija: 16:03, 4. april 2009
Urejanje z zlivanjem (angleško MergeSort) je stabilen algoritem za urejanje podatkov, ki ga je leta 1945 razvil John von Neumann.
Delovanje
Algoritem uporablja paradigmo deli in vladaj. Začne s podtabelami velikosti 1, ki so same po sebi seveda urejene. Nato začne z zlivanjem(in sprotnim urejanjem) parov podtabel v večjo podtabelo in te tabele nato zopet zliva v večje, dokler ne zlije vseh elementov tabele v eno urejeno tabelo.
Zahtevnost
Časovna zahtevnost je v vseh primerih , prostorska zahtevnost pa je , saj za podtabele potrebujemo dodaten prostor. Algoritem je možno implementirati tudi s prostorsko zahtevnostjo , a pri tem izgubimo stabilnost algortima.