Aufgabe
Ausgangssituation
Ihr Ausbildungsbetrieb wartet die Anwendung LagerSortierTool für einen mittelständischen Großhändler. Das Tool sortiert Artikellisten einzelner Lagerzonen nach Regalplatznummer, damit das Kommissionierpersonal die Wege effizient abläuft. In einem internen Code-Review wurde die bestehende Sortierroutine beanstandet, da sie bei großen Artikellisten spürbar langsam reagiert.
Ihnen liegt folgender Auszug aus der bestehenden Implementierung vor:
METHODE sortiereRegalplaetze(array, n)
FUER i VON 0 BIS n-1
FUER j VON 0 BIS n-1
WENN array[j] > array[j+1] DANN
tausche(array[j], array[j+1])
ENDE WENN
ENDE FUER
ENDE FUER
ENDE METHODE
Zusätzlich plant die Projektleitung, für eine andere Komponente des Tools, die Stücklistenauflösung von Mehrweg-Transportbehältern, eine rekursive Lösung einzusetzen. Eine Stückliste kann dabei beliebig viele Unterbehälter enthalten, die selbst wieder Unterbehälter enthalten.
a) Analyse der bestehenden Sortierroutine (4 Punkte)
Betrachten Sie den oben abgebildeten Pseudocode-Auszug.
Erläutern Sie zwei Schwachstellen dieser Implementierung, die – auch bei Beibehaltung des Sortierverfahrens Bubble Sort – unnötigen Mehraufwand bei der Ausführung verursachen.
b) Korrigierte Implementierung (6 Punkte)
Erstellen Sie einen vollständigen Pseudocode für eine korrigierte Methode sortiereRegalplaetzeOptimiert(array, n), die nach dem Prinzip des Bubble Sort arbeitet, die in a) erläuterten Schwachstellen vermeidet und bei einer bereits sortierten Liste frühzeitig abbricht.
c) Rekursive Stücklistenauflösung (6 Punkte)
Für die Komponente zur Stücklistenauflösung von Mehrweg-Transportbehältern soll eine rekursive Methode ermittleGesamtanzahl(behaelter) entstehen. Ein Behälter besitzt das Attribut anzahlEigeneTeile sowie eine Liste unterbehaelter, die weitere Behälter-Objekte desselben Typs enthalten kann. Die Methode soll die Gesamtzahl aller Teile liefern, die in einem Behälter und sämtlichen seiner Unterbehälter – über beliebig viele Ebenen hinweg – enthalten sind.
ca) Pseudocode der rekursiven Methode (4 Punkte)
Erstellen Sie einen vollständigen Pseudocode für die Methode ermittleGesamtanzahl(behaelter), der Basisfall und Rekursionsfall korrekt abbildet.
cb) Rekursionstiefe (2 Punkte)
Nennen Sie zwei Risiken, die bei unkontrollierter Rekursionstiefe dieser Methode in der betrieblichen Praxis auftreten können.
d) Vergleich der Laufzeit (4 Punkte)
Die Projektleitung möchte verstehen, warum sich der Umstieg auf die in b) erstellte Methode überhaupt lohnt.
Erläutern Sie anhand der Begriffe Best Case und Worst Case, wie sich die Laufzeit von Bubble Sort in Abhängigkeit vom Ausgangszustand der Artikelliste unterscheidet.
▶Musterlösung anzeigen
Musterlösung
a) Analyse der bestehenden Sortierroutine (4 Punkte)
Schwachstelle 1 – kein Abbruchkriterium: Die äußere Schleife durchläuft stets alle n Durchgänge, selbst wenn das Array bereits nach wenigen Durchgängen vollständig sortiert ist. Es fehlt eine Prüfung, ob im aktuellen Durchlauf noch mindestens ein Tausch stattgefunden hat – ohne diese Prüfung kann der Algorithmus nicht vorzeitig terminieren. (2 Punkte)
Schwachstelle 2 – unnötige Vergleiche am Listenende: Die innere Schleife läuft bei jedem Durchgang bis n-1, obwohl nach jedem abgeschlossenen Durchgang das jeweils größte verbleibende Element bereits an seiner endgültigen Position steht. Dadurch werden bei jedem weiteren Durchgang bereits korrekt einsortierte Elemente am Ende erneut unnötig verglichen. (2 Punkte)
(Hinweis, nicht Teil der geforderten zwei Effizienz-Schwachstellen, aber fachlich relevant: Der Code weist zusätzlich einen Indexfehler auf, da bei j = n-1 auf array[n] zugegriffen wird, was außerhalb des gültigen Indexbereichs liegt und zu einem Laufzeitfehler führen kann.)
b) Korrigierte Implementierung (6 Punkte)
METHODE sortiereRegalplaetzeOptimiert(array, n)
i = 0
getauscht = WAHR
SOLANGE i < n-1 UND getauscht == WAHR
getauscht = FALSCH
FUER j VON 0 BIS n-2-i
WENN array[j] > array[j+1] DANN
tausche(array[j], array[j+1])
getauscht = WAHR
ENDE WENN
ENDE FUER
i = i + 1
ENDE SOLANGE
ENDE METHODE
Bewertungskriterien:
- Reduzierte innere Schleifengrenze n-2-i, sodass bereits einsortierte Elemente am Ende nicht erneut geprüft werden und zugleich der Indexfehler des Originalcodes behoben wird (2 Punkte)
- Merker-Variable getauscht, die pro Durchlauf zurückgesetzt und bei jedem Tausch gesetzt wird (2 Punkte)
- Abbruchbedingung der äußeren Schleife über getauscht, sodass bei sortierter Liste kein weiterer Durchlauf erfolgt (2 Punkte)
c) Rekursive Stücklistenauflösung (6 Punkte)
ca) Pseudocode der rekursiven Methode (4 Punkte)
METHODE ermittleGesamtanzahl(behaelter)
gesamt = behaelter.anzahlEigeneTeile
FUER JEDEN unterbehaelter IN behaelter.unterbehaelter
gesamt = gesamt + ermittleGesamtanzahl(unterbehaelter)
ENDE FUER
RUECKGABE gesamt
ENDE METHODE
Bewertungskriterien:
- Basisfall korrekt abgebildet: Ein Behälter ohne Unterbehälter liefert direkt anzahlEigeneTeile zurück, da die Schleife dann nicht durchlaufen wird (2 Punkte)
- Rekursionsfall korrekt abgebildet: Für jeden Unterbehälter wird die Methode erneut aufgerufen und das Ergebnis zur Gesamtsumme addiert (2 Punkte)
cb) Rekursionstiefe (2 Punkte)
- Stacküberlauf (Stack Overflow): Bei sehr tief verschachtelten Behälterstrukturen kann die Anzahl der gleichzeitig offenen Methodenaufrufe den verfügbaren Aufrufstapel überschreiten, was zum Programmabsturz führt. (1 Punkt)
- Endlosrekursion bei fehlerhaften Stammdaten: Enthält ein Behälter durch einen Datenfehler direkt oder indirekt sich selbst (zyklische Referenz), terminiert die Rekursion nie; das Programm hängt bzw. bricht mit Stacküberlauf ab. (1 Punkt)
d) Vergleich der Laufzeit (4 Punkte)
Beim Best Case liegt die Artikelliste bereits vollständig sortiert vor. Die innere Schleife des optimierten Algorithmus stellt bereits im ersten Durchlauf fest, dass kein Tausch notwendig war, wodurch getauscht auf FALSCH bleibt und die äußere Schleife sofort abbricht. Es wird nur ein einziger Durchlauf mit linearem Aufwand (O(n)) benötigt. (2 Punkte)
Beim Worst Case liegt die Artikelliste in exakt umgekehrter Reihenfolge vor. In diesem Fall muss bei jedem der n-1 Durchläufe mindestens ein Tausch vorgenommen werden, sodass der vorzeitige Abbruch über getauscht nie greift und alle n-1 Durchläufe mit insgesamt n·(n-1)/2 Vergleichen ausgeführt werden. Die Anzahl der Vergleiche wächst dann quadratisch mit der Anzahl der Artikel (O(n²)), da sich innere und äußere Schleife gegenseitig multiplizieren. Die ursprüngliche Routine benötigt dagegen unabhängig vom Ausgangszustand immer n·n Vergleiche, also auch bei bereits sortierter Liste O(n²); der Umstieg lohnt sich daher vor allem bei (nahezu) sortierten Listen. (2 Punkte)