Merge Sort
Results 1 to 7 of 7

Thread: Merge Sort

  1. #1
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Merge Sort

    hi,
    ich verstehe nicht ganz wie der rekursive aufruf von merge sort funktioniert.kann mir das jemand mal erklären (am besten mit beispiel)?
    ALL GLORY TO THE HYPNO TOAD...

  2. #2
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also soweit ich das verstanden habe teilt der algorithmus merge-sort (seite 33) das array solange auf (immer halbieren) bis nur noch arrays mit einem element da sind.

    der algorithmus merge (seite 34) nimmt dann immer 2 arrays bzw deren elemente und sortiert sie und fügt sie in ein neues array (mit doppelter größe) ein.

    also aus [3, 5, 8, 1] werden 4 arrays [3] [5] [8] [1] diese werden dann rekursiv wieder zusammengefügt und gleichzeitig sortiert aus [3] [5] wird [3,5] aus [8] [1] wird [1,8] und schließlich aus [3,5] und [1,8] wird [1,3,5,8]

    hoffe ich erzähl kein stuß

  3. #3
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja den merge verstehe ich ja,und auch wie es prinzipiel funktionieren soll,aber wie das mit dem code gehen soll ist mir ein rätsel:
    denn der code terminiert ja wenn es nur eine einelementige menge ist.
    ALL GLORY TO THE HYPNO TOAD...

  4. #4
    Länz's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Ja das stimmt schon allerdings terminiert wird bei einer einelementigen Teilmenge die Methode Merge-Sort, d.h. erst wenn beide rekursiven Aufrufe von Merge-Sort termiert sind wird zum ersten Mal Merge aufgerufen (beim ersten Mal werden 2 einelementigeMengen "verschmolzen") wenn nun unser Input länger als zwei ist befinden wir uns natürlich noch immer in der Rekursion, d.h. nach dem ersten Merge verlassen wir die "innerste" Ebene und unser "Ergebnis"(=2elementige sortierte Teilfolge) wird dem Aufruf von Merge-Sort(damals mit 2Elementen) zurückgegeben nun wird Merge-Sort ein zweites Mal rekursiv für die linke Seite aufgerufen.....(bis auch eine 2elementige sortierte Teilfolge zurückgeliefert wird) - danach wird Merge zum dritten Mal, diesmal mit 2 sortierten zweielemntigen Teilfolgen aufgerufen............


    garnicht so leicht zu erklären das Zeugs, hoffe es war halbwegs verständlich!

  5. #5

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    533
    Thanks
    3
    Thanked 121 Times in 76 Posts
    vielleicht kann das Applet, das ich geschrieben hab, ein bisschen helfen:

    http://stud3.tuwien.ac.at/~e9726400/...ierApplet.html

    links kann man wählen, welche Sortieralgorithmen verwendet werden sollen;
    rechts kann man wählen, welche Informationen ausgegeben werden sollen;

    oben gibt man die Folge ein: ganze Zahlen getrennt durch Beistriche und/oder Leerzeichen; dann drückt man ENTER oder auf den Sortiere-Knopf;

    ich hab versucht, die rekursiven Aufrufe bei Merge-Sort möglichst verständlich auszugeben.
    wähle rechts nur die Informationen, die dich interessieren, sonst wird die Ausgabe vielleicht zu unübersichtlich.
    und beginne mit kurzen Folgen.

    ich hoffe, man kennt sich aus.

  6. #6
    AntiBit's Avatar
    Title
    Super Moderator
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Dimitrij, hiermit ernenne ich dich einfach nur zum Freak! *ui ui ui*
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  7. #7

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    533
    Thanks
    3
    Thanked 121 Times in 76 Posts
    Original geschrieben von AntiBit
    Dimitrij, hiermit ernenne ich dich einfach nur zum Freak! *ui ui ui*
    oh, vielen dank

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
  •