Mergesort: Übungen – Informatik Leistungskurs

Dein Fortschritt:

0 / 0 Aufgaben

Übungsaufgaben

Dreißig Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.

Stimmt's? — Eigenschaften von Mergesort

AFB I

Gib für jede Aussage über Mergesort an, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.

Aussage 1 von 5

Mergesort ist schnell und stabil, bezahlt das aber mit Speicher für die Hilfsreihung.

Ansatz: Denke an die drei Schritte und daran, wo verglichen wird.

Weiter: Stabil heißt: Gleiche Werte behalten ihre Reihenfolge.

Wie das Mischen funktioniert

AFB I

Beschreibe das Mischen zweier sortierter Hälften, indem du die Lücken füllst.

Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück. Achtung: 2 Wörter bleiben übrig.

Zwei stehen auf den Anfängen der beiden sortierten Hälften. Das der beiden Elemente kommt in die , dann rückt sein Zeiger vor. Ist eine Hälfte leer, wird der der anderen ohne übernommen. Am Ende wird die Hilfsreihung in den Bereich .

Beim Mischen wird immer das kleinere Front-Element übernommen — so entsteht die aufsteigende Folge.

Ansatz: Folge dem Ablauf im Quelltext von mische: zwei Indizes, eine Schleife, zwei Rest-Schleifen, Zurückkopieren.

Weiter: Sortiert wird aufsteigend — welches Element muss dann vorne stehen?

Zwei Hälften mischen

AFB I

Die sortierten Hälften sind 6, 19, 33 und 4, 21, 25, 40. Wende das Mischen an: Trage in jeder Zeile den übernommenen Wert ein und gib die Zahl der Vergleiche an.

Fülle alle Felder aus und prüfe dann. Enter in einem Feld prüft ebenfalls.

Vergleich	a[i]	a[j]
1	6	4
2	6	21
3	19	21
4	33	21
5	33	25
6	33	40
Rest	leer	40
Vergleiche

Nach dem sechsten Vergleich ist die linke Hälfte leer; 40 wird ohne Vergleich angehängt. Ergebnis: 4, 6, 19, 21, 25, 33, 40 — mit 6 Vergleichen bei 7 Elementen.

Ansatz: In jeder Zeile gewinnt der kleinere der beiden Werte.

Weiter: Die Zeile „Rest“ zählt nicht als Vergleich.