Kunfanda ordigo: Malsamoj inter versioj
[nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
e roboto aldono de: sl:Urejanje z zlivanjem |
SieBot (diskuto | kontribuoj) e roboto aldono de: ar:تصنيف دمجي |
||
Linio 35: | Linio 35: | ||
[[Kategorio:Algoritmoj de ordigo]] |
[[Kategorio:Algoritmoj de ordigo]] |
||
[[ar:تصنيف دمجي]] |
|||
[[bg:Сортиране чрез сливане]] |
[[bg:Сортиране чрез сливане]] |
||
[[cs:Merge sort]] |
[[cs:Merge sort]] |
Kiel registrite je 06:27, 26 apr. 2009
La algoritmo pri Kunfanda Ordigo (Merge sort en la angla) estas stabila eksterordiga algoritmo bazita sur la tekniko dividu kaj venkos. Ĝia komplekso estas O(n log n).
Priskribo
Estis prilaborita je 1945 far John von Neumann.
Superrigarde, la algoritmo temas pri dividi je du samgrandaj partoj la ordigotan vektoron, ordigi ĉiun parton aparte, kaj poste kunigi ambaŭ partojn ĝustorde en nur unu ordigitan vektoron.
Jene oni montras la algoritmon (atentu ke ne konsideras specialajn okazojn kiel vakuan vektoron, ktp; serioza realigo devas konsideri tiajn okazojn):
function mergesort(array A[0..n]) begin array A1 := mergesort(A[0..(int(n / 2))]) array A2 := mergesort(A[int(1 + n / 2)..n]) return merge(A1, A2) end function merge(array A1[0..n1], array A2[0..n2]) begin integer p1 := 0 integer p2 := 0 array R[0..(n1 + n2 + 1)] while (p1 <= n1 or p2 <= n2): if (p1 <= n1 and A1[p1] <= A2[p2]): R[p1 + p2] := A1[p1] p1 := p1 + 1 if (p2 <= n2 and A1[p1] > A2[p2]): R[p1 + p2] := A2[p2] p2 := p2 + 1 return R end