Stabilität Mergesort

Neue Frage »

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?
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »