Urejanje z zlivanjem: Razlika med redakcijama

Izbrisana vsebina Dodana vsebina

Znotrajvrstično

Redakcija: 21:03, 11. marec 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 $O(n\log n)$ , prostorska zahtevnost pa je $O(n)$ , saj za podtabele potrebujemo dodaten prostor. Algoritem je možno implementirati tudi s prostorsko zahtevnostjo $O(1)$ , a pri tem izgubimo stabilnost algortima.

Psevdokoda

Ta članek o računalništvu je škrbina. Pomagajte Wikipediji in ga razširite.

@@ Vrstica 18: / Vrstica 18: @@
 [[Kategorija:Algoritmi za urejanje podatkov]]
-[[ar:تصنيف دمجي]]
-[[bg:Сортиране чрез сливане]]
-[[cs:Merge sort]]
-[[de:Mergesort]]
-[[el:Ταξινόμηση με συγχώνευση]]
-[[en:Merge sort]]
-[[eo:Kunfanda ordigo]]
-[[es:Ordenamiento por mezcla]]
-[[et:Mestimissortimine]]
-[[fa:مرتب‌سازی ادغامی]]
-[[fi:Lomituslajittelu]]
-[[fr:Tri fusion]]
-[[he:מיון מיזוג]]
-[[hy:Միաձուլման տեսակավորում]]
 [[id:Urut gabung]]
-[[is:Sameiningarröðun]]
-[[it:Merge sort]]
-[[ja:マージソート]]
-[[kk:Тоғыстыру арқылы сүрыптау]]
-[[ko:합병 정렬]]
-[[lb:Mergesort]]
-[[lt:Sąlajos rikiavimo algoritmas]]
-[[ml:മെർജ് സോർട്ട്]]
-[[nl:Mergesort]]
 [[no:Sorteringsalgoritme#Flettesortering]]
-[[pl:Sortowanie przez scalanie]]
-[[pt:Merge sort]]
-[[ro:Merge sort]]
-[[ru:Сортировка слиянием]]
-[[sk:Triedenie zlučovaním]]
-[[tr:Birleştirmeli sıralama]]
-[[uk:Сортування злиттям]]
-[[vi:Sắp xếp trộn]]
-[[zh:归并排序]]