03.02.2021, 16:07 |
rummeldummel |
Auf diesen Beitrag antworten » |
Stabilität Mergesort
Meine Frage:
Aufgabe auf Bild.
Meine Ideen:
Ich habe leider keinen Ansatz. Könnte mir jemand etwas helfen? |
03.02.2021, 17:30 |
HAL 9000 |
Auf diesen Beitrag antworten » |
Es ist schwierig, dir jenseits von Banalitäten Hinweise zu geben, solange uns die dir vermutlich vorliegende detaillierte Ausformulierung des Mergesort-Algortithmus nicht bekannt ist. Wenn ich mal den Pseudocode auf https://de.wikipedia.org/wiki/Mergesort betrachte, dann ist das die entscheidende Stelle:
code: |
1:
2:
3:
4:
5:
|
if l[il] <= r[i-il] then
append l[il] to y
il := il+1
else
append r[i-il] to y |
|
Die Alternative
code: |
1:
2:
3:
4:
5:
|
if r[i-il] <= l[il] then
append r[i-il] to y
else
append l[il] to y
il := il+1 |
|
sortiert die Liste ebenfalls "richtig", aber nicht mehr stabil. |