Mergesort

Vu Wikipedia, der fräier Enzyklopedie.

Mergesort ass ee séiert allgemengt Zortéierverfahren, dat 1945 vum John von Neumann virgestallt ginn ass. Et handelt sech em ee rekursivt, stabilt awer net in-place Zortéierverfahren, dat nom Divide and Conquer-Prinzip schafft.

Inhaltsverzeechnes 1 Funktiounsweis 2 Algorithmus 3 Lafzäit 4 Literatur

[Änneren] Funktiounsweis

Mergesort ass eng speziell Uwennung von enger allgemenger Virgehensweis fir rekursiv Algorithmen.

D'Prinzip vun Divide and Counquer huet dräi Schrëtt:

1. Divide: De Problem gëtt an eng Zuel vu gläichgroussen Deelproblemer zerluecht.
2. Conquer: Deelproblemer ginn duerch Rekursioun (duerch Opruff vum selwechten Algorithmus) geléist.
3. Combine: Déi eenzel Léisunge ginn zu enger Gesamtléisung vum Originalproblem nees zesumme gesat. Hei gëtt déi eegentlech Aarbecht gemaach.

Bei Mergesort bedeit dëst:

1. Divide: Mergesort spléckt een Tableau A[1..n] vun n Elementer, déi zortéiert solle ginn, an zwee Deeler vun der Gréisst n / 2 op.
2. Conquer: Déi zwee Deeltableaue gi rekursiv duerch Mergesort zortéiert.
3. Combine: Merge mëscht déi zwee zortéiert Deeltableaue, sou datt se eng zortéiert Sequenz arginn.

[Änneren] Algorithmus

De folgende Pseudocode stellt eng Implementéierung vum Algorithmus dur:

Mergesort(A,p,r)
        if p<r then
                q := (p+r)/2
                Mergesort(A,p,q)
                Mergesort(A,q+1,r)
                Merge(A,p,q,r)
        fi
end

Prozedur Merge

Merge(A,p,q,r)
        i := p
        j := q+1
        k := p
        while i<=m and j<=r do
                if A[i]<A[j] then
                        B[k] := A[i]
                        i := i+1
                else
                        B[k] := A[j]
                        j := j+1
                fi
                k := k+1
        od

        while i<=m do
                B[k] := A[i]
                i := i+1
                k := k+1
        od

        while j<=r do
                B[k] := A[j]
                j := j+1
                k := k+1
        od

        // Kopéiere vum Tableau B nees an den Tableau A
        for i:=p to r do
                A[i] := B[i]
        od
end

[Änneren] Lafzäit

[Änneren] Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 1990.