Urejanje z zlivanjem: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m r2.7.1) (robot Dodajanje: el:Ταξινόμηση με συγχώνευση |
m r2.7.3) (Robot: Spreminjanje id:Merge sort v id:Urut gabung |
||
Vrstica 32: | Vrstica 32: | ||
[[he:מיון מיזוג]] |
[[he:מיון מיזוג]] |
||
[[hy:Միաձուլման տեսակավորում]] |
[[hy:Միաձուլման տեսակավորում]] |
||
[[id: |
[[id:Urut gabung]] |
||
[[is:Sameiningarröðun]] |
[[is:Sameiningarröðun]] |
||
[[it:Merge sort]] |
[[it:Merge sort]] |
Redakcija: 11:24, 1. januar 2013
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.