Mergesort

Vu Wikipedia
Wiesselen op: Navigatioun, sichen
Computer n screen.svg Dësen Informatiksartikel ass eréischt just eng Skizz. Wann Dir méi iwwer dëst Thema wësst, sidd Dir häerzlech invitéiert, aus dëse puer Sätz e richtegen Artikel ze schreiwen. Wann Dir Hëllef braucht beim Schreiwen, da luusst bis an d'FAQ eran.

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.

Funktiounsweis[änneren | Quelltext änneren]

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 eigentlech 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 erginn.

Algorithmus[änneren | Quelltext änneren]

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

Lafzäit[änneren | Quelltext änneren]

Literatur[änneren | Quelltext änneren]

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