MINT üben

Mergesort

Eine Bestenliste und zwei Lager voller Bestellungen — beide Male ist das Mischen sortierter Folgen der Schlüssel.

Dein Fortschritt:
0 / 0 Aufgaben
1

Die Bestenliste

14 BEAFB I–II

Ein Sportverein führt nach jedem Turnier eine Bestenliste. Die Punktzahlen stehen unsortiert in der Reihung punkte und sollen mit Mergesort (Quelltext aus dem Unterricht, mergesort(a, links, rechts) und mische(a, links, mitte, rechts)) aufsteigend sortiert werden.

Reihung punkte (Länge 6)
  1. Beschreiben Sie die Arbeitsweise von Mergesort nach dem Prinzip Teile und herrsche. (3 BE)
  2. Stellen Sie den Ablauf von mergesort(punkte, 0, 5) grafisch dar: erst alle Zerlegungen bis zu den Einzelelementen, dann alle Mischvorgänge mit ihrem Ergebnis. (5 BE)
  3. Geben Sie für den letzten Aufruf von mische an, welche Elemente verglichen werden, und nennen Sie die Anzahl der Vergleiche. (2 BE)
  4. Erläutern Sie am Beispiel der Bestenliste, was „stabil“ bedeutet und warum Mergesort durch a[i] <= a[j] in mische stabil ist. Die Spieler seien vorher alphabetisch sortiert. (4 BE)

Hinweise

Hinweis zu Aufgabe a)
Teilen, rekursiv sortieren, mischen — und der Basisfall.
Hinweis zu Aufgabe b)
mitte = (0 + 5) / 2 = 2: Die Hälften haben je drei Elemente und werden ungleich weitergeteilt.
Hinweis zu Aufgabe c)
Die Hälften vor dem letzten Mischen sind 27, 38, 41 und 12, 30, 45.
Hinweis zu Aufgabe d)
Was passiert mit zwei Spielern gleicher Punktzahl?