Merge Sort
Results 1 to 13 of 13

Thread: Merge Sort

  1. #1

    Title
    Master
    Join Date
    Mar 2002
    Posts
    163
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Merge Sort

    Habe da in alten Prüfungsaangaben eine Aufgabe zu MergeSort gefunden, da steht
    "Führen sie das Sortierverfahren Merge Sort and der folgenden Folge durch; 21,14,28,8,17,36,15,18,5,2
    geben sie dabei bei jedem Aufruf der Prozedur Merge (A,l,r,m) die Index-grenzen l,r und m, sowie die Folge davor und danach an.

    Bedeuted das dann, dass ich bei der Verschmelzung immer die Mitte bzw die Rechte und Linke Indexgrenze angeben soll?

  2. #2

    Title
    Master
    Join Date
    Apr 2002
    Posts
    112
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Das ist nichts anderes als:

    21,14,28,8,17,36,15,18,5,2

    Merge (A, 1, 1, 2)

    14,21,28,8,17,36,15,18,5,2

    Merge (A, 1, 2, 3)

    14,21,28,8,17,36,15,18,5,2

    Merge (A, 4, 4, 5)

    14,21,28,8,17,36,15,18,5,2

    Merge (A, 1, 3, 5)

    8,14,17,21,28,36,15,18,5,2

    Merge (A, 6, 6, 7)

    8,14,17,21,28,15,36,18,5,2

    Merge (A, 6, 7, 8)

    8,14,17,21,28,15,18,36,5,2

    Merge (A, 9, 9, 10)

    8,14,17,21,28,15,18,36,2,5

    Merge (A, 6, 8, 10)

    8,14,17,21,28,2,5,15,18,36

    Merge (A, 1, 5, 10)

    2,5,8,14,15,17,18,21,28,36

    (Fett geschrieben immer der Teilabschnitt der Folge, der mit dem letzten Aufruf sortiert wird)

    Wie immer: Kritik bei Fehlern erwünscht ...

  3. #3
    Kenny's Avatar
    Title
    Special User
    Join Date
    Jan 2002
    Location
    wien 23
    Posts
    507
    Thanks
    0
    Thanked 0 Times in 0 Posts
    vorher musst die folge natürlich aufteilen bis jeder teil nur mehr aus einer zahl besteht

    (DIVIDE & conquer)
    ciao.Markus

    http://www.mworx.at - Markus Jerko Photography

  4. #4

    Title
    Master
    Join Date
    Mar 2002
    Posts
    163
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thx

  5. #5
    bluefoxx's Avatar
    Title
    Baccalaureus
    Join Date
    Mar 2002
    Location
    Vienna
    Posts
    537
    Thanks
    0
    Thanked 0 Times in 0 Posts
    sollte die zerteilte folge nach dem erstem mal "mergen" nicht so aussehen?

    14 21 8 28 17 36 15 18 2 5

    ich will ja bei der ersten verschmelzung jeweils 2 elemente zusammenfügen, wobei das kleinere immer links stehen sollte... oder hab ich da was falsch interpretiert?

    MfG bFXx
    MfG

    bLu3

  6. #6

    Title
    Master
    Join Date
    Apr 2002
    Posts
    112
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von Kenny
    vorher musst die folge natürlich aufteilen bis jeder teil nur mehr aus einer zahl besteht

    (DIVIDE & conquer)
    stimmt, aber in dem Fall wird Merge() nicht aufgerufen, da l < r sein muss ... und es war nur gefragt, wann Merge() aufgerufen wird.

    Original geschrieben von bluefoxx
    sollte die zerteilte folge nach dem erstem mal "mergen" nicht so aussehen?

    14 21 8 28 17 36 15 18 2 5

    ich will ja bei der ersten verschmelzung jeweils 2 elemente zusammenfügen, wobei das kleinere immer links stehen sollte... oder hab ich da was falsch interpretiert?
    nein ... mergesort ruft sich rekursiv auf ...
    die erste teilfolge die abgearbeitet wird mittels mergesort ist die kleinste linke teilmenge, dann folgt die rechtsdavon, dann die kombination der beiden ... usw.
    stell es dir wie die postorder-durchmusterung von binären bäumen vor

  7. #7
    bluefoxx's Avatar
    Title
    Baccalaureus
    Join Date
    Mar 2002
    Location
    Vienna
    Posts
    537
    Thanks
    0
    Thanked 0 Times in 0 Posts
    *LICHTAUFGEH*

    Danke an den/die Mann/Frau ohne Gesicht!

    bFXx
    MfG

    bLu3

  8. #8

    Title
    Veteran
    Join Date
    Mar 2002
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    merge-sort aufteilen einer 10-teiligen folge

    hab da ein kleines problem...

    geg: 10, 65, 32, 87, 88, 86, 33, 4, 44, 44

    beim ersten aufteilen zerfällt die folge in 2 teilen mit 5 gliedern

    (10, 65, 32, 87, 88) (86, 33, 4, 44, 44)

    beim 2.mal würde ich das vorschlagen...

    (10, 65) (32, 87, 88) (86, 33) (4, 44, 44)

    und beim 3.mal

    (10) (65) (32) (87, 88) .....

    funkt es so???

  9. #9

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    780
    Thanks
    25
    Thanked 18 Times in 8 Posts

    Re: merge-sort aufteilen einer 10-teiligen folge

    Original geschrieben von malusmike

    (10, 65, 32, 87, 88) (86, 33, 4, 44, 44)

    beim 2.mal würde ich das vorschlagen...

    (10, 65) (32, 87, 88) (86, 33) (4, 44, 44)

    glaub eher das zerfällt in

    (10, 65, 32) (87, 88) (86, 33, 4) (44, 44)

    dann würd imho kommen

    (10,65)(32) (87) ( 88) (86,33)(4) (44) (44)
    und beim letzten mal alle in eins...

    aber ma muss sich des rekursiv überlegen..is nachher für die abarbeitung wichtig.

    obs for oder nach der hälfte geteilt wird hängt vom source code ab( im buch wird abgerundet)

    grüsse
    laborg

  10. #10

    Title
    Veteran
    Join Date
    Mar 2002
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts
    danke dir!

  11. #11

    Title
    Master
    Join Date
    Mar 2002
    Posts
    163
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Zerteilen tut der ALgorithmus Mergesort einfach immer l+r/2 abegrundet, wobei die Liste immer bei 1 beginnt, z.B.: das oben genannte Beispiel; 10 Elemente in der Liste --> l=1, r=10 m=5, im Zweiten Schritt ist es l=1, r=5 m=3 usw

  12. #12
    feurio's Avatar
    Title
    Master
    Join Date
    Feb 2002
    Location
    dada-istan
    Posts
    172
    Thanks
    22
    Thanked 23 Times in 14 Posts
    jumper ist das was du schreibst nicht widersprüchlich?
    wenn ich abrunde, sollte es dann folgendermassen lauten

    abr=abrunden
    abrunden heisst für mich auf den nächst kleineren ganzen zahl abrunden, wenn das ergebnis nicht eine ganze zahl ist.


    1-10 ..... abr(10/2) =5
    1-5 ........ abr(5/2) =abr(2,5) =2 oder irre ich mich da?

  13. #13

    Title
    Principal
    Join Date
    Dec 2001
    Posts
    88
    Thanks
    0
    Thanked 0 Times in 0 Posts

    ähm

    > oder irre ich mich da?
    ja

    die formel ist: abr((l+r)/2)

    1..10: (1+10)/2=5,5 -> 5
    1..5: (1+5)/2=3 -> 3

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •