Urejanje z zlivanjem: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m robot Spreminjanje: no:Sorteringsalgoritme#Flettesortering |
m robot Spreminjanje: ml:മെർജ് സോർട്ട് |
||
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
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.