Urejanje z zlivanjem: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
pravopis |
odstr. IW |
||
Vrstica 26: | Vrstica 26: | ||
[[Kategorija:Algoritmi za urejanje podatkov]] |
[[Kategorija:Algoritmi za urejanje podatkov]] |
||
[[no:Sorteringsalgoritme#Flettesortering]] |
Trenutna redakcija s časom 10:48, 24. februar 2017
Urejanje z zlivanjem | |
---|---|
Osnovni podatki | |
Vrsta: | algoritem za urejanje podatkov |
Podatkovna struktura: | tabela |
Časovna zahtevnost | |
Zgornja meja zahtevnosti: | O(n log n) |
Spodnja meja zahtevnosti: | O(n log n) |
Pričakovana zahtevnost: | O(n log n) |
Prostorska zahtevnost | |
Prostorska zahtevnost: | O(n) |
Urejanje z zlivanjem (angleško MergeSort) je stabilen algoritem za urejanje podatkov, ki ga je leta 1945 razvil John von Neumann.
Delovanje[uredi | uredi kodo]
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[uredi | uredi kodo]
Č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.