Kunfanda ordigo: Malsamoj inter versioj
[nekontrolita versio] | [nekontrolita versio] |
Enhavo forigita Enhavo aldonita
SieBot (diskuto | kontribuoj) e roboto aldono de: ar:تصنيف دمجي |
e roboto aldono de: fa:مرتبسازی ادغامی |
||
Linio 41: | Linio 41: | ||
[[en:Merge sort]] |
[[en:Merge sort]] |
||
[[es:Ordenamiento por mezcla]] |
[[es:Ordenamiento por mezcla]] |
||
[[fa:مرتبسازی ادغامی]] |
|||
[[fi:Lomituslajittelu]] |
[[fi:Lomituslajittelu]] |
||
[[fr:Tri fusion]] |
[[fr:Tri fusion]] |
Kiel registrite je 07:51, 16 maj. 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