0 Daumen
46 Aufrufe

Folgendes Array soll rekusive gelöst werden  array = { 9 1 7 3 8 2 6 4 }. Wie würde das Array nach jedem Merge-Schritt aussehen.

Meine Lösung:

{ 9 1 7 3 8 2 4 6}, {9 1 7 3 2 8 4 6}, {9 1 3 7 2 8 4 6}, {1 9 3 7 2 8 4 6}, { 1 9 3 7 2 4 6 8}, { 1 3 7 9 2 4 6 8}, { 1 2 3 4 5 6 7 8 9}

Für mich ist hier nur wichtig, dass ich verstehe, in welcher Reihenfolge vorgegangen wird. Wenn ich die Teilprobleme rekursive löse, sollten meine Zwischenergebnisse stimmen.

LG

Gefragt von

1 Antwort

+1 Punkt
 
Beste Antwort
Für mich ist hier nur wichtig, dass ich verstehe, in welcher Reihenfolge vorgegangen wird.

Lasse Dir dafür die einzelnen Steps am besten einmal mit diesem Tool anzeigen:

https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/

Beantwortet von 7,9 k

Hab es jetzt handschriftlich noch ein mal gemacht. Sollte wohl so aussehen:

{ 1 9 7 3 8 2 6 4 }

{ 1 9 3 7 8 2 6 4 }

{ 1 3 7 9 8 2 6 4 }

{ 1 3 7 9 2 8 6 4 }

{ 1 3 7 9 2 4 6 8 }

{ 1 2 3 4 6 7 8 9 }

Wobei man sich beim dividen nicht wirklich an den Algo halten muss, da erst beim Mergen die Reihenfolge verändert wird, oder?

Mein Merge-Sort ist so definiert:

Merge-Sort (A,p,r)

if(p < r)
q = (p+r)/2 //(abgerundet)
Merge-Sort(A,p,q)
Merge-Sort(A,q+1,r)
Merge(A,p,q,r)

Das heißt, dass meine linke Hälfte immer die kleinere bei ungeraden Längen ist und das umgekehrt zum Algo im Link ist, oder?

Danke für den Link, gleich abgespeichert.

LG

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

+1 Punkt
1 Antwort
0 Daumen
0 Antworten

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...