Urejanje z zlivanjem: Razlika med redakcijama

Iz Wikipedije, proste enciklopedije
Izbrisana vsebina Dodana vsebina
ArthurBot (pogovor | prispevki)
SieBot (pogovor | prispevki)
Vrstica 36: Vrstica 36:
[[lb:Mergesort]]
[[lb:Mergesort]]
[[lt:Sąlajos rikiavimo algoritmas]]
[[lt:Sąlajos rikiavimo algoritmas]]
[[ml:മെർജ് സോർട്ട്]]
[[ml:മെര്‍ജ് സോര്‍ട്ട്]]
[[nl:Mergesort]]
[[nl:Mergesort]]
[[no:Sorteringsalgoritme#Flettesortering]]
[[no:Sorteringsalgoritme#Flettesortering]]

Redakcija: 00:37, 7. februar 2010

Grafični prikaz urejanja z zlivanjem
Potek urejanja sedmih števil s rekurzivno implementacijo urejanja z zlivanjem

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.

Psevdokoda