Übungsaufgaben zu Sortieralgorithmen und Vergleichsfunktionen

https://bildung.social/@oerinformatik/

https://oer-informatik.de/sortieralgorithmen-uebungsaufgaben

Sortieralgorithmen, Bubblesort, Selectionsort, Insertionsort, Vergleichsfunktion, Stabilität, Schreibtischtest, Struktogramm, Übungsaufgaben, Prüfungsvorbereitung

tl/dr; (Bearbeitungszeit insgesamt 139 min, mehrere Aufgaben): Vier Übungsaufgaben zu Sortieralgorithmen. Zum Einstieg zwei kürzere Aufgaben: Uhrzeiten mit Ganzzahldivision und Modulo zerlegen, Bereichsbedingungen beurteilen, einen fehlerhaften Bubblesort per Schreibtischtest korrigieren, ein Überwachungsskript mit Start- und Endwerten vervollständigen und mehrere Arrays gemeinsam sortieren. Danach folgen zwei umfangreiche Aufgaben: Schreibtischtest und Lückencode, Bubblesort über Objekte, Vergleichsfunktionen mit Kommazahlen und mehreren Kriterien, Insertionsort mit einem Comparator, Sortieren mit Java- und Python-Bibliothek, Filtern und zweistufig Sortieren in einer Funktion, Entfernen im Durchlauf, sortiertes Einfügen, Sortieren über ein Index-Array, Stabilität und Laufzeit. Alle Lösungen sind ausgeblendet und mit Punkteverteilung versehen [AI-Assisted]. (Zuletzt geändert am 29.10.2026)

Diese Übungsaufgaben gehören zum Artikel Sortieralgorithmen und Vergleichsfunktionen. Die Grundmuster für Arrays (Durchlaufen, Zählen, Extremwerte) erklärt der Artikel Prozedurale Algorithmen mit Arrays.

Hinweise zur Bearbeitung: Als FIA oder FISY musst Du zur Teil-2-Prüfung Aufgaben auf Kernkompetenz-Ebene lösen können, das sind Aufgabe 2.1 und Aufgabe 2.2. Von FIA wird zusätzlich erwartet, dass ihnen Aufgaben auf Profilkompetenz-Ebene (Aufgabe 3.1 und Aufgabe 3.2) keine Probleme bereiten. Wenn nichts anderes verlangt ist, darfst Du Deine Algorithmen in Pseudocode, als Struktogramm oder als Programmablaufplan angeben. Arrays und Listen beginnen mit dem Index 0; Variablen musst Du nicht deklarieren. Fertige Sortierfunktionen einer Programmiersprache darfst Du nicht verwenden, wenn ein Sortieralgorithmus verlangt ist. Die Beispiellösungen verwenden die Schreibweise aus dem Artikel (:= für die Zuweisung, = und <> für Vergleiche, zähle i von a bis b mit eingeschlossener Obergrenze). Die Aufgabentexte nennen die Datentypen wie in den Klassendiagrammen (int, real, Text); in den Beispiellösungen stehen dafür die Typen der jeweiligen Notation, im deutschen Pseudo-Pascal also integer, double und string. Andere korrekte Lösungen sind ebenfalls richtig. Schreib Deine Lösung zuerst vollständig auf, bevor Du die Beispiellösung aufklappst.

Die Codebeispiele kannst Du in vier Notationen anzeigen. Die Notationen sind im Artikel Algorithmen mit Pseudocode dokumentieren beschrieben.

int anzahl = length(zeiten)
for (int i = 0 … anzahl-1) {
    write(zeiten[i])
}

anzahl: integer := length(zeiten)
for i := 0 to anzahl - 1 do
    writeln(zeiten[i])
end for

anzahl: integer := laenge(zeiten)
zähle i von 0 bis anzahl - 1
    Ausgabe zeiten[i]
Ende zähle

Du möchtest eigene Aufgaben zum Üben von einem KI-Sprachmodell generieren lassen?

Kopiere den Text in ein KI-Sprachmodell Deiner Wahl und passe Kompetenzstufe, Anzahl, Bearbeitungszeit und Szenario bei Bedarf an. Wie die Aufgaben aufgebaut sind, beschreibt der Artikel Wie sind die Aufgaben aufgebaut?. Prüfe die Ergebnisse mit dem Lehrartikel: KI-Sprachmodelle machen Fehler.

Erstelle neue Übungsaufgaben zum Thema „Sortieralgorithmen und
Vergleichsfunktionen“.

Bauplan: Halte Dich an Aufbau, Kompetenzstufen, Operatoren,
Anforderungsbereiche, Punkte und Zeitschätzung, die im Artikel
https://oer-informatik.de/aufgaben-aufbau beschrieben sind.

Fachliche Grundlage:
- https://oer-informatik.de/sortieralgorithmen
- https://oer-informatik.de/algorithmen-prozedural
- https://oer-informatik.de/algorithmen-objektorientiert
- https://oer-informatik.de/laufzeit-komplexitaet
- Stilbeispiel: https://oer-informatik.de/sortieralgorithmen-uebungsaufgaben

Die Aufgaben sollen Inhalte zu diesen Schlagwörtern abdecken:
- Sortieralgorithmen
- Bubblesort
- Selectionsort
- Insertionsort
- Vergleichsfunktion
- Stabilität
- Schreibtischtest
- Struktogramm

Kompetenzstufe: Kernkompetenz (alternativ: Basiskompetenz, Profilkompetenz, Expertise)
Anzahl: 1 Aufgabe mit Teilaufgaben
Bearbeitungszeit in Minuten ca.: <5 bis 30 min>
Szenario: eines der Szenarien aus dem Bauplan

Vorgehen:
1. Lies zuerst die verlinkten Artikel. Kannst Du keine Webseiten
   abrufen, sag mir das, statt zu raten.
2. Steht bei einer Angabe noch ein Platzhalter in <…>, frag mich
   zuerst danach. Richte Punkte und Zahl der Teilaufgaben nach der
   Bearbeitungszeit (ca. 0,9 min je Punkt).
3. Gib je Aufgabe Titel mit Kompetenzstufe, Ausgangssituation und
   Teilaufgaben mit Operator und Punktzahl aus, dazu die geschätzte
   Bearbeitungszeit.
4. Gib die Beispiellösungen mit Punkteverteilung erst aus, wenn ich
   danach frage.

Aufgabe 2.1: Rückfahrten am Flurmonitor prüfen und ordnen (Kernkompetenz)

(ca. 17 min Bearbeitungszeit)

Die Flurmonitore der Mitfahr-App RatzFahrt am Ratz und Rübe Berufskolleg sollen nachmittags die Rückfahrten ins Umland anzeigen, die früheste oben. Im Inserat speichert die App die Abfahrtszeit als ganze Zahl im Format hhmm: 1415 steht für 14:15 Uhr, 905 für 9:05 Uhr. Du entwickelst die Anzeige zusammen mit Deiner Mit-Azubi Oksana Melnyk. In Java liefert / bei ganzen Zahlen den ganzzahligen Anteil der Division und % den Rest.

a) Gib für eine Abfahrtszeit zeit je einen Ausdruck für die Stunde, für die Minute und für die Minuten seit Mitternacht an. Berechne damit, wie viele Minuten zwischen 13:50 Uhr und 14:15 Uhr liegen, und erkläre, warum 1415 - 1350 ein falsches Ergebnis liefert. (5 Punkte)

int stunde = zeit / 100;                    // 1415 / 100 = 14
int minute = zeit % 100;                    // 1415 % 100 = 15
int minutenSeitMitternacht = stunde * 60 + minute;

je Ausdruck 1 Punkt (gleichwertig: zeit / 100 * 60 + zeit % 100)
13:50 Uhr sind 13 · 60 + 50 = 830 Minuten, 14:15 Uhr sind 855 Minuten; dazwischen liegen 25 Minuten (1 Punkt).
1415 - 1350 = 65: Die beiden rechten Stellen zählen nur bis 59, die Zahl springt aber von 1359 auf 1400. Die Differenz rechnet so, als hätte eine Stunde 100 Minuten (1 Punkt).

b) Der Flurmonitor soll nur Rückfahrten zeigen, die zwischen 13:00 Uhr und 17:30 Uhr (jeweils einschließlich) starten. Weil Inserate früher von Hand eingetragen wurden, stehen im Bestand auch unsinnige Werte wie 1275. Oksana schlägt drei Bedingungen vor:

(1)  zeit >= 1300 || zeit <= 1730
(2)  zeit >= 1300 && zeit <= 1730
(3)  zeit >= 1300 && zeit <= 1730 && zeit % 100 < 60

Beurteile jede Bedingung mit je einem passenden Testwert und entscheide, welche in die App kommt. (4 Punkte)

1. ist für jede Zahl wahr, z. B. auch für 1745: Jede Zahl ist mindestens 1300 oder höchstens 1730. Die Oder-Verknüpfung filtert nichts (1 Punkt).
(2) prüft beide Grenzen richtig mit Und, lässt aber 1575 durch – eine Uhrzeit mit 75 Minuten (1 Punkt).
(3) schließt zusätzlich unmögliche Minutenwerte aus: 1575 % 100 = 75 ist nicht kleiner als 60 (1 Punkt).
Einbauen: Bedingung (3); 1300 und 1730 liegen als Grenzwerte noch im Bereich (1 Punkt).

c) Für die Reihenfolge auf dem Monitor hat Oksana einen Bubblesort geschrieben. Die Rückfahrten liegen lückenlos im Array zeiten.

void sortiereAbfahrten(int[] zeiten) {
    int n = zeiten.length;
    for (int d = 0; d < n - 1; d++) {
        for (int i = 1; i < n - 1 - d; i++) {
            if (zeiten[i] > zeiten[i + 1]) {
                zeiten[i] = zeiten[i + 1];
                int hilf = zeiten[i];
                zeiten[i + 1] = hilf;
            }
        }
    }
}

Mit den Testdaten {1540, 1315, 1505, 1640, 1300} zeigt der Monitor danach {1540, 1300, 1300, 1300, 1300}.

ca) Ermittle mit einem Schreibtischtest den Inhalt des Arrays nach dem ersten Durchlauf der äußeren Schleife (d = 0). (3 Punkte)

`i`	Vergleich	Wirkung	`zeiten` danach
1	1315 > 1505? nein	–	`{1540, 1315, 1505, 1640, 1300}`
2	1505 > 1640? nein	–	`{1540, 1315, 1505, 1640, 1300}`
3	1640 > 1300? ja	1300 wird nach vorne kopiert, 1640 geht verloren	`{1540, 1315, 1505, 1300, 1300}`

1 Punkt für den Start bei i = 1, 2 Punkte für das Array nach dem Durchlauf.

cb) Beschreibe die beiden Fehler und gib die korrigierten Anweisungen an. (4 Punkte)

Startwert der inneren Schleife: Mit i = 1 wird das Element auf Index 0 nie verglichen; 1540 bleibt vorne stehen. Korrektur: for (int i = 0; i < n - 1 - d; i++) (2 Punkte).
Reihenfolge im Tausch: Der linke Wert wird überschrieben, bevor er in hilf gesichert ist; danach steht der kleinere Wert doppelt im Array, der größere fehlt. Korrektur (Ringtausch, 2 Punkte):

int hilf = zeiten[i];
zeiten[i] = zeiten[i + 1];
zeiten[i + 1] = hilf;

Mit beiden Korrekturen ergibt sich {1300, 1315, 1505, 1540, 1640}.

d) Oksana fragt, ob man vor dem Sortieren nicht erst alle Zeiten in Minuten seit Mitternacht umrechnen müsste. Begründe, ob der direkte Vergleich der hhmm-Zahlen für die Sortierung ausreicht. (2 Punkte)

Für die Reihenfolge reicht der direkte Vergleich: Eine spätere Stunde ergibt immer eine um mindestens 100 größere Zahl, und innerhalb einer Stunde wächst die Zahl mit der Minute (die Minute ist kleiner als 60) (1 Punkt). Für Abstände wie in a) muss dagegen umgerechnet werden, weil die Differenz zweier hhmm-Zahlen keine Minutenzahl ist (1 Punkt).

Aufgabe 2.2: Last der Container überwachen (Kernkompetenz)

(ca. 26 min Bearbeitungszeit)

Die Let’s Meet GmbH betreibt ihre App in fünf Containern (api, web, chat, suche, bilder). Jeder Container zählt seit seinem Start alle beantworteten Anfragen und alle fehlgeschlagenen Anfragen in je einem Zähler, der nur wächst. Entwicklungsleiter Yusuf Demir bittet Dich und Deinen Mit-Azubi Jonas Weber, ein Überwachungsskript zu vervollständigen, das alle 10 Sekunden die Last je Container anzeigt – der am stärksten belastete Container oben.

Zeile 1   container := ["api", "web", "chat", "suche", "bilder"]
Zeile 2   zähle i von 0 bis 4
Zeile 3       start[i] := leseAnfragen(container[i])
Zeile 4       fehlerStart[i] := leseFehler(container[i])
Zeile 5   Ende zähle
Zeile 6   wiederhole
Zeile 7       warte(10 s)
Zeile 8       zähle i von 0 bis 4
Zeile 9           ende[i] := leseAnfragen(container[i])
Zeile 10          fehlerEnde[i] := leseFehler(container[i])
Zeile 11          last[i] := ______________________          // Anfragen je Sekunde
Zeile 12          quote[i] := ______________________         // Fehlerquote in Prozent
Zeile 13          ______________________                     // Werte für den
Zeile 14          ______________________                     // nächsten Durchlauf
Zeile 15      Ende zähle
Zeile 16      sortiereAbsteigend(container, last, quote)
Zeile 17      zeige(container, last, quote)
Zeile 18  solange das Skript nicht beendet wird

a) Ergänze die Zeilen 11 und 12. Die Fehlerquote ist der Anteil der fehlgeschlagenen an allen Anfragen der letzten 10 Sekunden. (5 Punkte)

Zeile 11          last[i] := (ende[i] - start[i]) / 10
Zeile 12          quote[i] := (fehlerEnde[i] - fehlerStart[i]) / (ende[i] - start[i]) * 100

Zeile 11: 1 Punkt Differenz, 1 Punkt Division durch 10 s. Zeile 12: je 1 Punkt für Zähler- und Nenner-Differenz, 1 Punkt für den Faktor 100. Der Absolutwert eines Zählers (ohne Differenz) ergibt keine Punkte für den Zähler bzw. Nenner, weil er alle Anfragen seit dem Start enthält.

b) Ergänze die Zeilen 13 und 14 und begründe, warum diese Zuweisungen nach den Zeilen 11 und 12 stehen müssen. (4 Punkte)

Zeile 13          start[i] := ende[i]
Zeile 14          fehlerStart[i] := fehlerEnde[i]

Je Zeile 1 Punkt (Reihenfolge der beiden Zeilen beliebig). Begründung (2 Punkte): Die Endwerte dieses Durchlaufs sind die Startwerte des nächsten. Würden sie vor der Berechnung übernommen, wären Start- und Endwert gleich – die Differenz und damit die Last wären immer 0 (bei der Quote sogar eine Division durch 0).

c) Jonas weist darauf hin, dass ein Container in 10 Sekunden auch einmal gar keine Anfrage bekommen kann. Beschreibe, welches Problem dann in Zeile 12 entsteht, und wie Du es behebst. (3 Punkte)

Ist ende[i] - start[i] = 0, wird durch 0 geteilt – je nach Sprache bricht das Skript ab oder liefert „unendlich“/„NaN“ (1 Punkt). Abhilfe (2 Punkte): vorher prüfen, z. B.

wenn ende[i] - start[i] > 0 dann
    quote[i] := (fehlerEnde[i] - fehlerStart[i]) / (ende[i] - start[i]) * 100
sonst
    quote[i] := 0
Ende wenn

d) Schreibe die Prozedur sortiereAbsteigend(namen: Text[], last: real[], quote: real[]), die die drei Arrays mit Bubblesort so umordnet, dass der Container mit der höchsten Last vorne steht. Name, Last und Fehlerquote eines Containers müssen dabei zusammenbleiben. (11 Punkte)

sortiereAbsteigend(String namen[], float last[], float quote[]) {
    int n = length(namen)
    for (int p = 0 … n-2) {
        for (int i = 0 … n-2-p) {
            if (last[i] < last[i + 1]) {
                float hilfZahl = last[i]
                last[i] = last[i + 1]
                last[i + 1] = hilfZahl
                String hilfName = namen[i]
                namen[i] = namen[i + 1]
                namen[i + 1] = hilfName
                hilfZahl = quote[i]
                quote[i] = quote[i + 1]
                quote[i + 1] = hilfZahl
            }
        }
    }
}

PROCEDURE sortiereAbsteigend(namen: array of String, last: array of real, quote: array of real)
    n: integer := length(namen)
    for p := 0 to n - 2 do
        for i := 0 to n - 2 - p do
            if (last[i] < last[i + 1]) then
                hilfZahl: real := last[i]
                last[i] := last[i + 1]
                last[i + 1] := hilfZahl
                hilfName: String := namen[i]
                namen[i] := namen[i + 1]
                namen[i + 1] := hilfName
                hilfZahl := quote[i]
                quote[i] := quote[i + 1]
                quote[i + 1] := hilfZahl
            end if
        end for
    end for
END sortiereAbsteigend

Prozedur sortiereAbsteigend(namen: string[], last: double[], quote: double[])
    n: integer := laenge(namen)
    zähle p von 0 bis n - 2
        zähle i von 0 bis n - 2 - p
            wenn last[i] < last[i + 1] dann
                hilfZahl: double := last[i]
                last[i] := last[i + 1]
                last[i + 1] := hilfZahl
                hilfName: string := namen[i]
                namen[i] := namen[i + 1]
                namen[i + 1] := hilfName
                hilfZahl := quote[i]
                quote[i] := quote[i + 1]
                quote[i + 1] := hilfZahl
            Ende wenn
        Ende zähle
    Ende zähle
Ende sortiereAbsteigend

2 Punkte äußere Schleife mit n - 1 Durchläufen.
2 Punkte innere Schleife: Zugriff auf i + 1 bleibt im Array (die Verkürzung um p ist nicht verlangt).
2 Punkte Vergleich der Last mit < (absteigend).
5 Punkte Tausch: Last 2, Name 2, Quote 1 Punkt. Wird nur last getauscht, passen Namen und Quoten nicht mehr zu den Werten.

Gleichwertig ist eine Lösung mit einem Array von Objekten (Name, Last, Quote), in der ganze Objekte getauscht werden.

e) Nach einem Durchlauf liegen diese Werte vor: Namen ["api", "web", "chat", "suche", "bilder"], Last [12.5, 40.0, 7.3, 40.0, 3.1]. Gib die Reihenfolge der Namen nach dem Sortieren an und begründe, warum web vor suche steht. (3 Punkte)

["web", "suche", "api", "chat", "bilder"] (2 Punkte). web und suche haben dieselbe Last. Getauscht wird nur bei echtem <, Elemente mit gleichem Wert werden nie vertauscht – Bubblesort ist so stabil, und die ursprüngliche Reihenfolge (web vor suche) bleibt erhalten (1 Punkt).

f) Bestimme, wie viele Vergleiche Dein Algorithmus bei fünf Containern in jedem Durchlauf des Skripts ausführt. (2 Punkte)

Die innere Schleife vergleicht 4 + 3 + 2 + 1 = 10-mal (allgemein \frac{n \cdot (n-1)}{2}) (1 Punkt Rechenweg, 1 Punkt Ergebnis). Ohne die Verkürzung um p wären es 4 · 4 = 16 Vergleiche.

Aufgabe 3.1: Nachbestellliste und Händlerportal im Fahrrad-Onlineshop (Profilkompetenz)

(ca. 54 min Bearbeitungszeit)

Du bist Auszubildende*r im IT-Team der CSB-Rad GmbH in Bielefeld. Cem Sarıkaya, Geschäftsführer Technik und IT, hat Dich für zwei Projekte eingeteilt: Im Projekt „Lager 4.0“ zeigen Tablets in Werkstatt und Lager künftig Listen an, und das neue Händlerportal soll den 37 Fachhändlern das Sortiment in verschiedenen Sortierungen anbieten. Jonas, Dein Mit-Azubi, arbeitet mit Dir zusammen.

Im Shop-Backend gibt es die Klasse Artikel:

Artikel
- artikelnr: Text
- bezeichnung: Text
- kategorie: Text          // Bezeichnung der Kategorie, z. B. "Bremsen"
- nettoPreis: real
- lagerbestand: int
- mindestbestand: int
+ getArtikelnr(): Text
+ getBezeichnung(): Text
+ getKategorie(): Text
+ getNettoPreis(): real
+ getLagerbestand(): int
+ getMindestbestand(): int

a) Die Werkstatt-Tablets zeigen die Montagezeiten der letzten Lastenräder in Minuten aufsteigend an. Ein Dienstleister hat dafür folgende Prozedur geliefert:

Prozedur sortiereZeiten(zeiten: integer[])
    ende := laenge(zeiten) - 1
    getauscht := true
    solange getauscht
        getauscht := false
        zähle j von 0 bis ende - 1
            wenn zeiten[j] > zeiten[j + 1] dann
                hilf := zeiten[j]
                zeiten[j] := zeiten[j + 1]
                zeiten[j + 1] := hilf
                getauscht := true
            Ende wenn
        Ende zähle
        ende := ende - 1
    Ende solange
Ende sortiereZeiten

aa) Ermittle mit einem Schreibtischtest für zeiten = [95, 40, 120, 40, 75] den Inhalt des Arrays sowie die Werte von getauscht und ende am Ende jedes Durchlaufs der solange-Schleife. Gib außerdem an, wie viele Vergleiche zeiten[j] > zeiten[j + 1] insgesamt ausgeführt werden. (4 Punkte)

Durchlauf	Vergleiche (getauscht in Klammern)	`zeiten` am Ende	`getauscht`	`ende`
(Start)	–	`[95, 40, 120, 40, 75]`	wahr	4
1	95/40 (getauscht), 95/120, 120/40 (getauscht), 120/75 (getauscht)	`[40, 95, 40, 75, 120]`	wahr	3
2	40/95, 95/40 (getauscht), 95/75 (getauscht)	`[40, 40, 75, 95, 120]`	wahr	2
3	40/40, 40/75	`[40, 40, 75, 95, 120]`	falsch	1

Nach dem dritten Durchlauf ist getauscht falsch, die Schleife endet. Insgesamt werden 4 + 3 + 2 = 9 Vergleiche ausgeführt.

Bewertung: je Durchlauf 1 Punkt (Array, getauscht und ende richtig), Anzahl der Vergleiche 1 Punkt.

ab) Nenne das Sortierverfahren und erläutere, welche Aufgabe die Variablen ende und getauscht haben. (3 Punkte)

Verfahren: Bubblesort (Sortieren durch Vertauschen benachbarter Elemente). (1 Punkt)
ende: Nach jedem Durchlauf steht das größte noch unsortierte Element am Ende des betrachteten Bereichs. ende verkleinert diesen Bereich um eins, damit bereits sortierte Elemente nicht erneut verglichen werden. (1 Punkt)
getauscht: merkt, ob im aktuellen Durchlauf mindestens einmal getauscht wurde. Gab es keinen Tausch, ist das Array sortiert, und die Schleife endet vorzeitig. Im Beispiel spart das einen vierten Durchlauf. (1 Punkt)

b) Natalia Wróbel aus der Buchhaltung möchte die offenen Posten nach Betrag absteigend sehen. Jonas hat dafür ein anderes Verfahren gewählt, aber nicht alle Zeilen fertig geschrieben:

Prozedur sortiereOffenePosten(betraege: double[])
    n := laenge(betraege)
    zähle i von 0 bis n - 2
        posMax := i
        (1) .........................................
            wenn (2) ............................... dann
                (3) .................................
            Ende wenn
        Ende zähle
        hilf := betraege[i]
        (4) .........................................
        (5) .........................................
    Ende zähle
Ende sortiereOffenePosten

ba) Ergänze die Lücken (1) bis (5). (6 Punkte)

(1) zähle j von i + 1 bis n - 1
(2) betraege[j] > betraege[posMax]
(3) posMax := j
(4) betraege[i] := betraege[posMax]
(5) betraege[posMax] := hilf

Bewertung: (1) 2 Punkte (Start bei i + 1 und Grenze n - 1, je 1 Punkt), (2) 1 Punkt (Richtung > für absteigend), (3) 1 Punkt, (4) und (5) zusammen 2 Punkte. Ein zusätzliches wenn posMax <> i um den Tausch ist richtig, aber nicht nötig.

bb) Nenne das Verfahren, das Jonas verwendet. (1 Punkt)

Selectionsort (Sortieren durch Auswählen): Im unsortierten Bereich wird das größte Element gesucht und an die erste unsortierte Position getauscht.

bc) In einer ersten Fassung hatte Jonas den Tausch so geschrieben:

betraege[i] := betraege[posMax]
betraege[posMax] := betraege[i]

Erläutere, welches Ergebnis dieser Tausch hat. (2 Punkte)

Nach der ersten Zeile steht der größte Betrag in beiden Feldern; der ursprüngliche Wert von betraege[i] ist überschrieben. Die zweite Zeile schreibt denselben Wert zurück. Danach enthält das Array den größten Betrag doppelt, der überschriebene Betrag fehlt (1 Punkt). Für den Tausch braucht man eine Hilfsvariable, die den alten Wert von betraege[i] zwischenspeichert (Ringtausch) (1 Punkt).

c) Bastian Ludwig, Leiter von Werkstatt und Einkauf, erhält jeden Morgen eine Nachbestellliste auf sein Tablet. Sie enthält alle Artikel, deren Lagerbestand unter dem Mindestbestand liegt, und ist bisher nach Artikelnummer sortiert. Künftig sollen die Artikel mit der größten Fehlmenge (Mindestbestand minus Lagerbestand) oben stehen. Die Liste vom 26.10.2026:

Nachbestellliste vom 26.10.2026
Index	Artikelnummer	Bezeichnung	Lagerbestand	Mindestbestand
0	BRE-BEL-02	Bremsbelag-Satz	4	15
1	BRE-HYD-01	Hydraulische Scheibenbremse (Paar)	9	12
2	KET-11-E	Kette 11-fach E-Bike	6	8
3	LIC-SET-01	Lichtset Nabendynamo StVZO	18	25
4	RAD-CITY-01	Stadtrad „Promenade“ 7-Gang	3	5
5	RAD-EB-02	E-Bike „Kanal“ Mittelmotor 500 Wh	1	3

ca) Erstelle einen Algorithmus für die Prozedur sortiereNachbestellung(artikel: Artikel[]), die das übergebene Array nach Fehlmenge absteigend sortiert. Verwende einen selbst geschriebenen Sortieralgorithmus und nenne das gewählte Verfahren. (10 Punkte)

Verfahren: Bubblesort

sortiereNachbestellung(Artikel artikel[]) {
    int n = length(artikel)
    for (int i = 0 … n-2) {
        for (int j = 0 … n-2-i) {
            int fehlLinks = artikel[j].getMindestbestand() - artikel[j].getLagerbestand()
            int fehlRechts = artikel[j + 1].getMindestbestand() - artikel[j + 1].getLagerbestand()
            if (fehlLinks < fehlRechts) {
                Artikel hilf = artikel[j]
                artikel[j] = artikel[j + 1]
                artikel[j + 1] = hilf
            }
        }
    }
}

PROCEDURE sortiereNachbestellung(artikel: array of Artikel)
    n: integer := length(artikel)
    for i := 0 to n - 2 do
        for j := 0 to n - 2 - i do
            fehlLinks: integer := artikel[j].getMindestbestand() - artikel[j].getLagerbestand()
            fehlRechts: integer := artikel[j + 1].getMindestbestand() - artikel[j + 1].getLagerbestand()
            if (fehlLinks < fehlRechts) then
                hilf: Artikel := artikel[j]
                artikel[j] := artikel[j + 1]
                artikel[j + 1] := hilf
            end if
        end for
    end for
END sortiereNachbestellung

Prozedur sortiereNachbestellung(artikel: Artikel[])
    n: integer := laenge(artikel)
    zähle i von 0 bis n - 2
        zähle j von 0 bis n - 2 - i
            fehlLinks: integer := artikel[j].getMindestbestand() - artikel[j].getLagerbestand()
            fehlRechts: integer := artikel[j + 1].getMindestbestand() - artikel[j + 1].getLagerbestand()
            wenn fehlLinks < fehlRechts dann
                hilf: Artikel := artikel[j]
                artikel[j] := artikel[j + 1]
                artikel[j + 1] := hilf
            Ende wenn
        Ende zähle
    Ende zähle
Ende sortiereNachbestellung

Bewertung:

Verfahren genannt: 1 Punkt
äußere Schleife mit richtiger Anzahl Durchläufe: 2 Punkte
innere Schleife mit Grenze ohne Zugriff hinter das Array-Ende: 2 Punkte
Fehlmenge für beide Artikel richtig berechnet (über die Getter): 2 Punkte
Vergleich in der richtigen Richtung (absteigend): 1 Punkt
Tausch ganzer Objekte mit Hilfsvariable: 2 Punkte

Selectionsort oder Insertionsort sind ebenso richtig. Die Optimierung - i in der inneren Schleife ist nicht verlangt.

cb) Gib die Reihenfolge der Artikelnummern an, die Dein Algorithmus für die Liste vom 26.10.2026 liefert. (2 Punkte)

Platz	Artikelnummer	Fehlmenge
1	BRE-BEL-02	11
2	LIC-SET-01	7
3	BRE-HYD-01	3
4	KET-11-E	2
5	RAD-CITY-01	2
6	RAD-EB-02	2

Der Bubblesort aus ca) tauscht nur bei echtem Kleiner (<). Die drei Artikel mit der Fehlmenge 2 behalten deshalb ihre bisherige Reihenfolge (nach Artikelnummer).

Bewertung: Reihenfolge nach Fehlmenge 1 Punkt, Reihenfolge der gleichen Fehlmengen passend zum eigenen Algorithmus 1 Punkt (bei Selectionsort kann sie abweichen).

d) Das Händlerportal ist in Java geschrieben. Ein Sortierkriterium ist dort ein Objekt vom Typ Comparator<Artikel>: Seine Methode compare(a, b) liefert einen negativen Wert, wenn a vor b gehört, 0 bei Gleichstand und einen positiven Wert, wenn a hinter b gehört. Eine Methode mit zwei Artikel-Parametern und int-Rückgabe kann per Methodenreferenz als Comparator<Artikel> übergeben werden; im Pseudocode übergibst Du einfach ihren Namen. Jonas hat für die Preisansicht (günstigster Artikel zuerst) diese Methode geschrieben:

int vergleichePreis(Artikel a, Artikel b) {
    return (int) (a.getNettoPreis() - b.getNettoPreis());
}

Im Test stehen das Rahmenschloss SCH-RAH-01 (41,18 €) und ein neues Faltschloss für 41,95 € in der Preisansicht mal so, mal so herum – je nachdem, in welcher Reihenfolge sie aus der Datenbank kommen.

da) Erkläre die Ursache an diesem Testfall und schreibe eine korrigierte Fassung von vergleichePreis. (6 Punkte)

Ursache (2 Punkte): Die Differenz 41,18 − 41,95 = −0,77 ist eine Kommazahl; die Umwandlung nach int schneidet die Nachkommastellen ab und liefert 0. Die beiden Schlösser gelten damit als gleich teuer, der Sortieralgorithmus lässt sie in der Reihenfolge stehen, in der sie ankommen. Das betrifft jeden Preisunterschied unter 1 €.

Korrigierte Fassung:

int vergleichePreis(Artikel a, Artikel b) {
    if (a.getNettoPreis() < b.getNettoPreis()) {
        return -1
    }
    if (a.getNettoPreis() > b.getNettoPreis()) {
        return 1
    }
    return 0
}

FUNCTION vergleichePreis(a: Artikel, b: Artikel) : integer
    if (a.getNettoPreis() < b.getNettoPreis()) then
        RETURN -1
    end if
    if (a.getNettoPreis() > b.getNettoPreis()) then
        RETURN 1
    end if
    RETURN 0
END vergleichePreis

Funktion vergleichePreis(a: Artikel, b: Artikel): integer
    wenn a.getNettoPreis() < b.getNettoPreis() dann
        Rückgabe -1
    Ende wenn
    wenn a.getNettoPreis() > b.getNettoPreis() dann
        Rückgabe 1
    Ende wenn
    Rückgabe 0
Ende vergleichePreis

Bewertung: Fall „a günstiger“ 2 Punkte, Fall „a teurer“ 1 Punkt, Fall „gleich“ 1 Punkt. Statt -1 und 1 sind beliebige negative bzw. positive Werte richtig. In Java ist auch return Double.compare(a.getNettoPreis(), b.getNettoPreis()); richtig.

e) Bevor das Portal die Sortierfunktion der Bibliothek nutzt, möchte Cem Sarıkaya an einem eigenen Algorithmus sehen, wie ein Comparator arbeitet.

ea) Erstelle die Prozedur sortiereMit(artikel: Artikel[], vergleich: Comparator<Artikel>), die das Array mit Insertionsort sortiert. Die Reihenfolge zweier Artikel darf nur über vergleich.compare(…) bestimmt werden. (8 Punkte)

sortiereMit(Artikel artikel[], Comparator<Artikel> vergleich) {
    for (int i = 1 … length(artikel)-1) {
        Artikel neu = artikel[i]
        int j = i - 1
        while (j >= 0 && vergleich.compare(artikel[j], neu) > 0) {
            artikel[j + 1] = artikel[j]            // größeres Element rückt nach hinten
            j = j - 1
        }
        artikel[j + 1] = neu
    }
}

PROCEDURE sortiereMit(artikel: array of Artikel, vergleich: Comparator<Artikel>)
    for i := 1 to length(artikel) - 1 do
        neu: Artikel := artikel[i]
        j: integer := i - 1
        while (j >= 0) AND (vergleich.compare(artikel[j], neu) > 0) do
            artikel[j + 1] := artikel[j]           // größeres Element rückt nach hinten
            j := j - 1
        end while
        artikel[j + 1] := neu
    end for
END sortiereMit

Prozedur sortiereMit(artikel: Artikel[], vergleich: Comparator<Artikel>)
    zähle i von 1 bis laenge(artikel) - 1
        neu: Artikel := artikel[i]
        j: integer := i - 1
        solange j >= 0 und vergleich.compare(artikel[j], neu) > 0
            artikel[j + 1] := artikel[j]           // größeres Element rückt nach hinten
            j := j - 1
        Ende solange
        artikel[j + 1] := neu
    Ende zähle
Ende sortiereMit

Bewertung:

äußere Schleife ab dem zweiten Element bis zum letzten: 2 Punkte
einzusortierendes Element zwischenspeichern: 1 Punkt
innere Schleife mit Grenze j >= 0 vor dem Zugriff: 2 Punkte
Vergleich nur über compare mit > 0 (der linke Artikel gehört hinter den neuen): 2 Punkte
Verschieben und Einsetzen an j + 1: 1 Punkt

Mit > 0 rückt der neue Artikel nicht an gleichwertigen vorbei; das Verfahren bleibt stabil.

eb) Im fertigen Portal liegt das Sortiment in der Java-Liste List<Artikel> sortiment, und die Bibliothek übernimmt das Sortieren. Gib je eine Anweisung an, die die Liste aufsteigend bzw. absteigend nach Nettopreis sortiert. Verwende Comparator.comparingDouble und reversed(). Ein Export-Skript erledigt dasselbe in Python; gib dort die beiden Aufrufe mit sorted und key an. (4 Punkte)

sortiment.sort(Comparator.comparingDouble(Artikel::getNettoPreis));              // aufsteigend
sortiment.sort(Comparator.comparingDouble(Artikel::getNettoPreis).reversed());   // absteigend

aufsteigend = sorted(sortiment, key=lambda a: a.getNettoPreis())
absteigend = sorted(sortiment, key=lambda a: a.getNettoPreis(), reverse=True)

Je Anweisung 1 Punkt. Gleichwertig in Java: sortiment.sort(this::vergleichePreis) mit der korrigierten Methode aus da) bzw. sortiment.sort((a, b) -> vergleichePreis(b, a)) für absteigend. Python übergibt keine Vergleichsfunktion, sondern eine Schlüsselfunktion, die für jedes Element den Sortierwert liefert; eine Vergleichsfunktion wie in da) lässt sich mit functools.cmp_to_key umwandeln. Beide Bibliotheken sortieren stabil.

f) Katarzyna Nowak, Einkäuferin eines Fachhändlers, wünscht sich im Portal eine Ansicht, die nach Kategorie alphabetisch sortiert ist und innerhalb einer Kategorie die teuersten Artikel zuerst zeigt. Zum Vergleich zweier Zeichenketten gibt es die Funktion vergleicheText(s1: Text, s2: Text) : int (negativ, wenn s1 alphabetisch vor s2 steht, 0 bei Gleichheit, sonst positiv).

Auszug aus dem Sortiment für das Händlerportal
Artikelnummer	Kategorie	Nettopreis (Listenpreis)
RAD-CITY-01	Stadträder	671,43 €
RAD-EB-02	E-Bikes	2.520,17 €
LIC-SET-01	Beleuchtung	75,63 €
BRE-HYD-01	Bremsen	133,61 €
BRE-BEL-02	Bremsen	18,40 €
SCH-BUE-01	Schlösser	62,18 €
SCH-RAH-01	Schlösser	41,18 €
KET-11-E	Antrieb	32,90 €

fa) Erstelle die Vergleichsfunktion vergleicheKategoriePreis(a: Artikel, b: Artikel) : int für diese Ansicht. Du darfst vergleichePreis aus d) verwenden. (5 Punkte)

int vergleicheKategoriePreis(Artikel a, Artikel b) {
    int ergebnis = vergleicheText(a.getKategorie(), b.getKategorie())
    if (ergebnis != 0) {
        return ergebnis                         // unterschiedliche Kategorien
    }
    return vergleichePreis(b, a)                // gleiche Kategorie: teurer zuerst
}

FUNCTION vergleicheKategoriePreis(a: Artikel, b: Artikel) : integer
    ergebnis: integer := vergleicheText(a.getKategorie(), b.getKategorie())
    if (ergebnis <> 0) then
        RETURN ergebnis                         // unterschiedliche Kategorien
    end if
    RETURN vergleichePreis(b, a)                // gleiche Kategorie: teurer zuerst
END vergleicheKategoriePreis

Funktion vergleicheKategoriePreis(a: Artikel, b: Artikel): integer
    ergebnis: integer := vergleicheText(a.getKategorie(), b.getKategorie())
    wenn ergebnis <> 0 dann
        Rückgabe ergebnis                       // unterschiedliche Kategorien
    Ende wenn
    Rückgabe vergleichePreis(b, a)              // gleiche Kategorie: teurer zuerst
Ende vergleicheKategoriePreis

Bewertung: Vergleich der Kategorien mit vergleicheText 2 Punkte, zweites Kriterium nur bei gleicher Kategorie 1 Punkt, Preis in absteigender Richtung (Argumente vertauscht oder Vorzeichen umgekehrt) 2 Punkte. Eine Lösung ohne vergleichePreis mit eigenen </>-Vergleichen ist ebenso richtig.

fb) Gib die Reihenfolge der acht Artikel an, die sortiereMit(sortiment, vergleicheKategoriePreis) aus ea) liefert. (2 Punkte)

Platz	Kategorie	Artikelnummer	Nettopreis
1	Antrieb	KET-11-E	32,90 €
2	Beleuchtung	LIC-SET-01	75,63 €
3	Bremsen	BRE-HYD-01	133,61 €
4	Bremsen	BRE-BEL-02	18,40 €
5	E-Bikes	RAD-EB-02	2.520,17 €
6	Schlösser	SCH-BUE-01	62,18 €
7	Schlösser	SCH-RAH-01	41,18 €
8	Stadträder	RAD-CITY-01	671,43 €

Bewertung: Kategorien in richtiger Reihenfolge 1 Punkt, innerhalb von Bremsen und Schlösser teurer zuerst 1 Punkt.

g) Cem Sarıkaya möchte vor dem Start des Portals zwei Fragen geklärt haben.

ga) Bastian Ludwig wünscht, dass Artikel mit gleicher Fehlmenge auf der Nachbestellliste weiterhin nach Artikelnummer geordnet sind. Erläutere den Begriff „stabiles Sortierverfahren“ und begründe, ob Dein Algorithmus aus ca) diesen Wunsch erfüllt. Gib an, was sich ändert, wenn die Bedingung fehlLinks <= fehlRechts lautet. (3 Punkte)

Ein Sortierverfahren ist stabil, wenn Elemente mit gleichem Sortierschlüssel nach dem Sortieren in derselben Reihenfolge stehen wie vorher. (1 Punkt)
Bubblesort mit < tauscht nur Nachbarn mit echt unterschiedlicher Fehlmenge; gleiche Fehlmengen werden nie gegeneinander getauscht. Weil die Liste nach Artikelnummer sortiert ankommt, bleibt diese Ordnung bei Gleichstand erhalten – der Wunsch ist erfüllt. (1 Punkt; bei Selectionsort: nicht garantiert, weil der Tausch ein Element über ein gleichwertiges hinweg verschieben kann)
Mit <= werden auch gleiche Nachbarn getauscht: Das Ergebnis ist weiterhin nach Fehlmenge sortiert, aber nicht mehr stabil (KET-11-E, RAD-CITY-01 und RAD-EB-02 erscheinen in umgekehrter Reihenfolge), und es wird unnötig getauscht. (1 Punkt)

Unabhängig vom Verfahren erfüllt eine mehrstufige Vergleichsfunktion (Fehlmenge absteigend, bei Gleichstand Artikelnummer aufsteigend) den Wunsch sicher.

gb) Für den Jahresabschluss sollen alle 4.800 Bestellpositionen des Jahres sortiert werden. Berechne, wie viele Vergleiche Bubblesort im ungünstigsten Fall benötigt und wie lange das bei 1 µs je Vergleich dauert. Vergleiche das Ergebnis mit einem Verfahren, das rund n \cdot \log_2 n Vergleiche benötigt. (4 Punkte)

Geg.: n = 4.800 Bestellpositionen; t_V = 1 µs je Vergleich
Ges.: Anzahl Vergleiche V, Dauer t (Bubblesort und n · log2 n)

\text{I: } V = \frac{n \cdot (n-1)}{2} \qquad \text{II: } t = V \cdot t_V

I in II:

t = \frac{n \cdot (n-1)}{2} \cdot t_V = \frac{4800 \cdot 4799}{2} \cdot 1\,\mathrm{\mu s} = 11\,517\,600\,\mathrm{\mu s} \approx \underline{\underline{11{,}518\,\mathrm{s}}}

Bubblesort benötigt also 11.517.600 Vergleiche.

Schnelles Verfahren:

V_{schnell} = n \cdot \log_2 n = 4800 \cdot \log_2 4800 \approx 4800 \cdot 12{,}229 \approx 58\,698

t_{schnell} = V_{schnell} \cdot t_V \approx 58\,698 \cdot 1\,\mathrm{\mu s} \approx \underline{\underline{0{,}059\,\mathrm{s}}}

Das schnelle Verfahren braucht weniger als ein Hundertstel der Zeit (Faktor rund 196). Bubblesort hat eine quadratische Laufzeit (O(n^2)); für große Datenmengen nimmt man deshalb ORDER BY in der Datenbank oder die Sortierfunktion der Programmiersprache.

Bewertung: Anzahl Vergleiche 1 Punkt, Dauer Bubblesort 1 Punkt, Vergleichswerte des schnellen Verfahrens 1 Punkt, Schlussfolgerung 1 Punkt.

Aufgabe 3.2: Vorschlagsliste, Tagesplan und Raumranking für ein Barcamp (Profilkompetenz)

(ca. 42 min Bearbeitungszeit)

Am Ratz und Rübe Berufskolleg (RRB) in Bielefeld findet am Samstag, 13.03.2027, das Barcamp „Lernen.Digital.Leben 2027“ statt. Du bist Auszubildende*r im Orga-Team und entwickelst mit Mia Schröder die Planungssoftware weiter. Dimitrios Papadopoulos leitet die Organisation.

Jede eingereichte Session wird von zwei Personen des Orga-Teams mit 1 bis 10 Punkten begutachtet. Gehen die beiden Gutachten weit auseinander, bespricht das Orga-Team die Session lieber noch einmal, bevor sie auf die Vorschlagsliste kommt. Die Planungssoftware stellt die Einreichungen als Objekte der Klasse Einreichung bereit:

Einreichung
- nr: int
- titel: Text
- format: Text              // "Vortrag", "Workshop", "Diskussion" oder "Tutorial"
- status: Text              // "eingereicht", "angenommen", "abgelehnt" oder "zurueckgezogen"
- punkteSchnitt: real       // Mittelwert der Gutachten, -1 wenn noch kein Gutachten vorliegt
- abweichung: real          // Unterschied der beiden Gutachten in Punkten, -1 ohne Gutachten
+ getNr(): int
+ getTitel(): Text
+ getFormat(): Text
+ getStatus(): Text
+ getPunkteSchnitt(): real
+ getAbweichung(): real

Das Array einreichungen ist nach dem Einreichungsdatum sortiert. Stand 25.11.2026 (Auszug):

Einreichungen zum Barcamp (Stand 25.11.2026)
Index	Nr.	Titel	Format	Status	Punkteschnitt	Abweichung
0	5	Datenschutz im Schulalltag – Mythen und Fakten	Diskussion	eingereicht	7,5	1
1	7	Krypto-Trading für Einsteiger	Vortrag	abgelehnt	2,0	0
2	32	Git für Einsteiger*innen	Workshop	eingereicht	8,5	3
3	33	Podcasts im Unterricht	Vortrag	eingereicht	6,0	2
4	34	Smart Home selbst bauen mit MQTT	Workshop	eingereicht	8,5	1
5	35	Ausbildung in Teilzeit	Diskussion	eingereicht	-1	-1
6	36	3D-Druck im Werkstattunterricht	Workshop	eingereicht	9,0	4
7	37	Prompting für Auszubildende	Tutorial	eingereicht	6,5	1
8	38	Linux auf alten Laptops	Workshop	zurueckgezogen	7,0	0

a) Für die Sitzungen des Orga-Teams soll eine Vorschlagsliste entstehen. Die Funktion vorschlagsliste(einreichungen: Einreichung[], mindestpunkte: real, maxAbweichung: real) : Einreichung[] gibt ein neues Array zurück. Es enthält nur Einreichungen, die noch den Status „eingereicht“ haben, mindestens mindestpunkte erreichen und deren Gutachten höchstens maxAbweichung Punkte auseinanderliegen. Das Array ist genau so lang, wie Einreichungen passen. Oben stehen die Sessions mit dem höchsten Punkteschnitt; bei gleichem Schnitt kommt die Session zuerst, bei der sich die Gutachten einiger sind. Neue Arrays legst Du mit neues Einreichung-Array der Länge n an; eine fertige Sortierfunktion der Programmiersprache verwendest Du hier nicht.

Beispiel: vorschlagsliste(einreichungen, 7.0, 3) liefert die Einreichungen 34, 32 und 5 in dieser Reihenfolge.

aa) Stelle den Algorithmus der Funktion als Struktogramm dar und nenne das Sortierverfahren, das Du verwendest. (12 Punkte)

Verfahren: Bubblesort

Struktogramm der Funktion vorschlagsliste: passende Einreichungen zählen, Array anlegen und füllen, nach Punkteschnitt und Abweichung sortieren (mit KI erstellt)

Dieselbe Lösung in Pseudocode:

Einreichung[] vorschlagsliste(Einreichung einreichungen[], float mindestpunkte, float maxAbweichung) {
    // 1. passende Einreichungen zählen
    int anzahl = 0
    for (int i = 0 … length(einreichungen)-1) {
        Einreichung e = einreichungen[i]
        if (e.getStatus() == "eingereicht" && e.getPunkteSchnitt() >= mindestpunkte
             && e.getAbweichung() <= maxAbweichung) {
            anzahl = anzahl + 1
        }
    }
    // 2. Array passender Länge anlegen und füllen
    Einreichung liste[anzahl]
    int k = 0
    for (int i = 0 … length(einreichungen)-1) {
        Einreichung e = einreichungen[i]
        if (e.getStatus() == "eingereicht" && e.getPunkteSchnitt() >= mindestpunkte
             && e.getAbweichung() <= maxAbweichung) {
            liste[k] = e
            k = k + 1
        }
    }
    // 3. Bubblesort: Schnitt absteigend, bei Gleichstand Abweichung aufsteigend
    for (int a = 0 … anzahl-2) {
        for (int j = 0 … anzahl-2-a) {
            Einreichung x = liste[j]
            Einreichung y = liste[j + 1]
            if (x.getPunkteSchnitt() < y.getPunkteSchnitt()
                 || (x.getPunkteSchnitt() == y.getPunkteSchnitt() && x.getAbweichung() > y.getAbweichung())) {
                liste[j] = y
                liste[j + 1] = x
            }
        }
    }
    return liste
}

FUNCTION vorschlagsliste(einreichungen: array of Einreichung, mindestpunkte: real, maxAbweichung: real) : array of Einreichung
    // 1. passende Einreichungen zählen
    anzahl: integer := 0
    for i := 0 to length(einreichungen) - 1 do
        e: Einreichung := einreichungen[i]
        if (e.getStatus() = "eingereicht") AND (e.getPunkteSchnitt() >= mindestpunkte)
             AND (e.getAbweichung() <= maxAbweichung) then
            anzahl := anzahl + 1
        end if
    end for
    // 2. Array passender Länge anlegen und füllen
    liste: array [0..anzahl - 1] of Einreichung
    k: integer := 0
    for i := 0 to length(einreichungen) - 1 do
        e: Einreichung := einreichungen[i]
        if (e.getStatus() = "eingereicht") AND (e.getPunkteSchnitt() >= mindestpunkte)
             AND (e.getAbweichung() <= maxAbweichung) then
            liste[k] := e
            k := k + 1
        end if
    end for
    // 3. Bubblesort: Schnitt absteigend, bei Gleichstand Abweichung aufsteigend
    for a := 0 to anzahl - 2 do
        for j := 0 to anzahl - 2 - a do
            x: Einreichung := liste[j]
            y: Einreichung := liste[j + 1]
            if (x.getPunkteSchnitt() < y.getPunkteSchnitt())
                 OR ((x.getPunkteSchnitt() = y.getPunkteSchnitt()) AND (x.getAbweichung() > y.getAbweichung())) then
                liste[j] := y
                liste[j + 1] := x
            end if
        end for
    end for
    RETURN liste
END vorschlagsliste

Funktion vorschlagsliste(einreichungen: Einreichung[], mindestpunkte: double, maxAbweichung: double): Einreichung[]
    // 1. passende Einreichungen zählen
    anzahl: integer := 0
    zähle i von 0 bis laenge(einreichungen) - 1
        e: Einreichung := einreichungen[i]
        wenn e.getStatus() = "eingereicht" und e.getPunkteSchnitt() >= mindestpunkte
             und e.getAbweichung() <= maxAbweichung dann
            anzahl := anzahl + 1
        Ende wenn
    Ende zähle
    // 2. Array passender Länge anlegen und füllen
    liste := neues Einreichung-Array der Länge anzahl
    k: integer := 0
    zähle i von 0 bis laenge(einreichungen) - 1
        e: Einreichung := einreichungen[i]
        wenn e.getStatus() = "eingereicht" und e.getPunkteSchnitt() >= mindestpunkte
             und e.getAbweichung() <= maxAbweichung dann
            liste[k] := e
            k := k + 1
        Ende wenn
    Ende zähle
    // 3. Bubblesort: Schnitt absteigend, bei Gleichstand Abweichung aufsteigend
    zähle a von 0 bis anzahl - 2
        zähle j von 0 bis anzahl - 2 - a
            x: Einreichung := liste[j]
            y: Einreichung := liste[j + 1]
            wenn x.getPunkteSchnitt() < y.getPunkteSchnitt()
                 oder (x.getPunkteSchnitt() = y.getPunkteSchnitt() und x.getAbweichung() > y.getAbweichung()) dann
                liste[j] := y
                liste[j + 1] := x
            Ende wenn
        Ende zähle
    Ende zähle
    Rückgabe liste
Ende vorschlagsliste

Einreichungen ohne Gutachten (-1) fallen bei jeder sinnvollen Mindestpunktzahl heraus. Weil 32 und 34 denselben Schnitt haben, entscheidet die Abweichung: 34 (1 Punkt Unterschied) steht vor 32 (3 Punkte), obwohl 32 früher eingereicht wurde. 36 hat zwar den höchsten Schnitt, die Gutachten liegen aber 4 Punkte auseinander.

Bewertung:

Verfahren genannt: 1 Punkt
passende Einreichungen zählen: 2 Punkte
Filterbedingung mit allen drei Teilen und UND: 2 Punkte
Array mit passender Länge anlegen und mit eigenem Zähler füllen: 2 Punkte
Sortierschleifen mit korrekten Grenzen: 2 Punkte
zweistufiger Vergleich (Schnitt absteigend, bei Gleichstand Abweichung aufsteigend): 2 Punkte
Tausch und Rückgabe: 1 Punkt

Andere Wege sind richtig, z. B. sortiertes Einfügen schon beim Füllen oder eine eigene Vergleichsfunktion für die beiden Kriterien.

ab) Gib an, welche Einreichungen in welcher Reihenfolge vorschlagsliste(einreichungen, 6.0, 2) liefert. (2 Punkte)

34, 5, 37, 33 (8,5 / 7,5 / 6,5 / 6,0). 32 und 36 fallen wegen der Abweichung heraus, 7 und 38 wegen des Status, 35 mangels Gutachten. 1 Punkt für die richtige Auswahl, 1 Punkt für die Reihenfolge.

b) Für eine Übersicht kopiert Mia die Einreichungen in eine Liste, die beim Entfernen schrumpft: liste.entferne(i) entfernt das Element an Position i, alle Elemente dahinter rücken um eins nach vorne (in Java liste.remove(i), in Python del liste[i]). Mit dieser Prozedur möchte sie alle Einreichungen entfernen, die nicht mehr den Status „eingereicht“ haben:

Prozedur nurOffene(liste: Liste von Einreichung)
    n := laenge(liste)
    zähle i von 0 bis n - 1
        wenn liste[i].getStatus() <> "eingereicht" dann
            liste.entferne(i)
        Ende wenn
    Ende zähle
Ende nurOffene

ba) Mia testet mit einer Liste aus den Einreichungen 38 (zurückgezogen), 7 (abgelehnt), 32 (eingereicht) und 35 (eingereicht). Ermittle mit einem Schreibtischtest, was passiert, und beschreibe die beiden Fehler. (3 Punkte)

n wird einmal zu Beginn auf 4 gesetzt.

i	`liste[i]`	Aktion	Liste danach
0	38 (zurückgezogen)	entfernen	7, 32, 35
1	32 (eingereicht)	–	7, 32, 35
2	35 (eingereicht)	–	7, 32, 35
3	existiert nicht	Zugriff hinter das Listenende	Laufzeitfehler

Fehler 1: Nach dem Entfernen rückt 7 auf Position 0 nach, i wird trotzdem auf 1 erhöht. Einreichung 7 wird nie geprüft und bleibt in der Liste. (1 Punkt)
Fehler 2: Die Obergrenze n - 1 wurde vor dem Entfernen berechnet. Weil die Liste kürzer geworden ist, greift die Schleife bei i = 3 auf ein Element zu, das es nicht mehr gibt (Python: IndexError). (1 Punkt)

Schreibtischtest: 1 Punkt.

bb) Korrigiere die Prozedur. (3 Punkte)

nurOffene(List<Einreichung> liste) {
    int i = 0
    while (i < liste.size()) {                   // Länge in jedem Durchlauf neu
        if (liste.get(i).getStatus() != "eingereicht") {
            liste.remove(i)                      // nächstes Element steht jetzt auf i
        } else {
            i = i + 1
        }
    }
}

PROCEDURE nurOffene(liste: List of Einreichung)
    i: integer := 0
    while (i < length(liste)) do                 // Länge in jedem Durchlauf neu
        if (liste[i].getStatus() <> "eingereicht") then
            liste.remove(i)                      // nächstes Element steht jetzt auf i
        else
            i := i + 1
        end if
    end while
END nurOffene

Prozedur nurOffene(liste: Liste von Einreichung)
    i: integer := 0
    solange i < laenge(liste)                    // Länge in jedem Durchlauf neu
        wenn liste[i].getStatus() <> "eingereicht" dann
            liste.entferne(i)                    // nächstes Element steht jetzt auf i
        sonst
            i := i + 1
        Ende wenn
    Ende solange
Ende nurOffene

Bewertung: Schleife mit aktueller Länge 1 Punkt, Index nur ohne Entfernen erhöhen 2 Punkte. Ebenso richtig: Durchlauf von hinten nach vorne (zähle i von laenge(liste) - 1 bis 0 Schrittweite -1) – dann verschieben sich nur bereits geprüfte Elemente. In Python geht es auch ohne Entfernen im Durchlauf: liste[:] = [e for e in liste if e.getStatus() == "eingereicht"].

c) Die Infomonitore zeigen den Tagesplan des Barcamps. Er liegt im Array plan: Eintrag[] mit 48 Plätzen; belegt sind die Positionen 0 bis anzahl - 1, aufsteigend sortiert nach Beginn. Die Klasse Eintrag bietet getBeginn(): int (Minuten seit Mitternacht, z. B. 11:00 Uhr = 660), getRaum(): Text und getTitel(): Text. Nach dem Barcamp-Prinzip werden am Morgen im Plenum spontan weitere Sessions ergänzt. Jede neue Session soll sofort an der richtigen Stelle im Plan stehen; Sessions mit gleichem Beginn erscheinen in der Reihenfolge, in der sie eingetragen wurden.

Tagesplan vor dem Plenum (anzahl = 5)
Index	Beginn	Raum	Titel
0	600	A.001	KI-Assistenten im Unterricht – was geht, was nicht?
1	660	C.110	Reparieren statt wegwerfen: Laptops retten
2	765	B.201	Barrierefreie Videos: Untertitel und Gebärdensprache
3	825	B.202	Escape-Room mit Mikrocontrollern
4	885	B.202	Barrierefreie Webseiten mit HTML und ARIA

ca) Erstelle einen Algorithmus für die Funktion fuegeEin(plan: Eintrag[], anzahl: int, neu: Eintrag) : int, die den Eintrag neu an der richtigen Stelle einfügt und die neue Anzahl zurückgibt. Ist der Plan voll, soll nichts eingefügt und -1 zurückgegeben werden. (8 Punkte)

int fuegeEin(Eintrag plan[], int anzahl, Eintrag neu) {
    if (anzahl >= length(plan)) {
        return -1
    }
    // Position suchen: hinter alle Einträge, die nicht später beginnen
    int pos = 0
    while (pos < anzahl && plan[pos].getBeginn() <= neu.getBeginn()) {
        pos = pos + 1
    }
    // Einträge ab pos von hinten nach vorne um eins verschieben
    int k = anzahl
    while (k > pos) {
        plan[k] = plan[k - 1]
        k = k - 1
    }
    plan[pos] = neu
    return anzahl + 1
}

FUNCTION fuegeEin(plan: array of Eintrag, anzahl: integer, neu: Eintrag) : integer
    if (anzahl >= length(plan)) then
        RETURN -1
    end if
    // Position suchen: hinter alle Einträge, die nicht später beginnen
    pos: integer := 0
    while (pos < anzahl) AND (plan[pos].getBeginn() <= neu.getBeginn()) do
        pos := pos + 1
    end while
    // Einträge ab pos von hinten nach vorne um eins verschieben
    k: integer := anzahl
    while (k > pos) do
        plan[k] := plan[k - 1]
        k := k - 1
    end while
    plan[pos] := neu
    RETURN anzahl + 1
END fuegeEin

Funktion fuegeEin(plan: Eintrag[], anzahl: integer, neu: Eintrag): integer
    wenn anzahl >= laenge(plan) dann
        Rückgabe -1
    Ende wenn
    // Position suchen: hinter alle Einträge, die nicht später beginnen
    pos: integer := 0
    solange pos < anzahl und plan[pos].getBeginn() <= neu.getBeginn()
        pos := pos + 1
    Ende solange
    // Einträge ab pos von hinten nach vorne um eins verschieben
    k: integer := anzahl
    solange k > pos
        plan[k] := plan[k - 1]
        k := k - 1
    Ende solange
    plan[pos] := neu
    Rückgabe anzahl + 1
Ende fuegeEin

Beispiel: Die spontane Session „Mastodon für Schulen“ um 11:00 Uhr (660) in A.105 wird an Position 2 eingefügt – hinter die Reparatur-Session, die ebenfalls um 11:00 Uhr beginnt. Die Funktion gibt 6 zurück; die Einträge mit Beginn 765, 825 und 885 stehen nun auf den Positionen 3 bis 5.

Bewertung:

Prüfung auf vollen Plan mit Rückgabe -1: 1 Punkt
Positionssuche mit Grenze pos < anzahl vor dem Zugriff: 2 Punkte
<= für die Reihenfolge bei gleichem Beginn: 1 Punkt
Verschieben von hinten nach vorne: 2 Punkte
Einfügen an pos und Rückgabe anzahl + 1: 2 Punkte

cb) Erläutere, warum die Einträge von hinten nach vorne verschoben werden müssen. (2 Punkte)

Beim Verschieben nach hinten wird jeweils die nächste Position überschrieben. Beginnt man hinten, ist die Zielposition anzahl frei bzw. bereits kopiert, sodass kein Eintrag verloren geht (1 Punkt). Beginnt man vorne mit plan[pos + 1] := plan[pos], wird der Eintrag auf pos + 1 überschrieben, bevor er selbst verschoben wurde; im nächsten Schritt wird der bereits kopierte Eintrag weiterkopiert – am Ende steht derselbe Eintrag auf allen Positionen ab pos (1 Punkt).

cc) Nenne das Sortierverfahren, das entsteht, wenn alle Sessions des Tages nacheinander mit fuegeEin in einen leeren Plan eingetragen werden. (1 Punkt)

Insertionsort (Sortieren durch Einfügen).

d) Dimitrios möchte sehen, welche Räume nach dem Anmeldestand voraussichtlich am stärksten ausgelastet sind. Die Planungssoftware liefert die durchschnittliche Auslastung über alle Slots in Prozent im Array auslastung: real[]; der Index eines Raums ist um 1 kleiner als seine raum_id.

Voraussichtliche Auslastung der Räume
Index	raum_id	Raum	`auslastung[i]`
0	1	A.001 Aula	62,5
1	2	A.104	93,8
2	3	A.105	62,5
3	4	B.012 Mensa	31,7
4	5	B.201 IT-Labor 1	87,5
5	6	B.202 IT-Labor 2	76,8
6	7	C.110 Elektrowerkstatt	45,8
7	8	C.020 Bibliothek	30,0

Die Funktion auslastungsranking(auslastung: real[]) : int[] soll ein Array ranking mit den raum_ids zurückgeben, geordnet nach Auslastung absteigend. Das Array auslastung bleibt dabei unverändert: Die Funktion legt ranking mit den Werten 1 bis n an und sortiert nur diese Nummern; die Auslastung eines Eintrags liest sie über auslastung[ranking[j] - 1] nach. Zum Sortieren soll folgendes Verfahren verwendet werden: Für jede Position i von der ersten bis zur vorletzten wird im Bereich von Position i bis zum Ende der Raum mit der höchsten Auslastung gesucht und mit Position i getauscht.

da) Stelle den Algorithmus der Funktion in Pseudocode, als Struktogramm oder als Programmablaufplan dar. (9 Punkte)

int[] auslastungsranking(float auslastung[]) {
    int n = length(auslastung)
    int ranking[n]
    for (int i = 0 … n-1) {
        ranking[i] = i + 1                       // raum_id
    }
    for (int i = 0 … n-2) {
        int posMax = i
        for (int j = i + 1 … n-1) {
            if (auslastung[ranking[j] - 1] > auslastung[ranking[posMax] - 1]) {
                posMax = j
            }
        }
        int hilf = ranking[i]                    // nur die raum_ids tauschen
        ranking[i] = ranking[posMax]
        ranking[posMax] = hilf
    }
    return ranking
}

FUNCTION auslastungsranking(auslastung: array of real) : array of integer
    n: integer := length(auslastung)
    ranking: array [0..n - 1] of integer
    for i := 0 to n - 1 do
        ranking[i] := i + 1                      // raum_id
    end for
    for i := 0 to n - 2 do
        posMax: integer := i
        for j := i + 1 to n - 1 do
            if (auslastung[ranking[j] - 1] > auslastung[ranking[posMax] - 1]) then
                posMax := j
            end if
        end for
        hilf: integer := ranking[i]              // nur die raum_ids tauschen
        ranking[i] := ranking[posMax]
        ranking[posMax] := hilf
    end for
    RETURN ranking
END auslastungsranking

Funktion auslastungsranking(auslastung: double[]): integer[]
    n: integer := laenge(auslastung)
    ranking := neues integer-Array der Länge n
    zähle i von 0 bis n - 1
        ranking[i] := i + 1                      // raum_id
    Ende zähle
    zähle i von 0 bis n - 2
        posMax: integer := i
        zähle j von i + 1 bis n - 1
            wenn auslastung[ranking[j] - 1] > auslastung[ranking[posMax] - 1] dann
                posMax := j
            Ende wenn
        Ende zähle
        hilf: integer := ranking[i]              // nur die raum_ids tauschen
        ranking[i] := ranking[posMax]
        ranking[posMax] := hilf
    Ende zähle
    Rückgabe ranking
Ende auslastungsranking

Ergebnis für die Beispieldaten: ranking = [2, 5, 6, 1, 3, 7, 4, 8] (A.104 mit 93,8 % vorne, die Bibliothek mit 30,0 % hinten).

Bewertung:

Array ranking anlegen und mit i + 1 füllen: 2 Punkte
äußere Schleife bis zur vorletzten Position: 1 Punkt
Suche des Maximums ab Position i mit Merken der Position: 2 Punkte
Vergleich über die nachgeschlagene Auslastung (auslastung[ranking[j] - 1]): 2 Punkte
Tausch der beiden Nummern über eine Hilfsvariable: 1 Punkt
Rückgabe: 1 Punkt

Wer die Auslastung über auslastung[j] statt über ranking[j] nachschlägt, vergleicht nach dem ersten Tausch die falschen Räume.

db) Dimitrios möchte, dass Räume mit gleicher Auslastung nach raum_id aufsteigend erscheinen. Gib den Inhalt von ranking nach dem zweiten Tausch (also nach i = 1) an und begründe damit, ob das vorgegebene Verfahren seinen Wunsch garantiert. Nenne eine Abhilfe. (3 Punkte)

Nach i = 0 (Tausch Position 0 mit Position 1): 2, 1, 3, 4, 5, 6, 7, 8. Nach i = 1 (Tausch Position 1 mit Position 4): 2, 5, 3, 4, 1, 6, 7, 8. (1 Punkt)
Raum 3 steht jetzt vor Raum 1, obwohl beide 62,5 % haben: Der Tausch hat Raum 1 über den gleichwertigen Raum 3 hinweg nach hinten geschoben. Dass am Ende doch 1 vor 3 steht, ist bei diesen Daten Zufall. Das Verfahren (Selectionsort) ist nicht stabil und garantiert den Wunsch nicht. (1 Punkt)
Abhilfe: bei gleicher Auslastung zusätzlich die Nummer vergleichen (… oder (gleiche Auslastung und ranking[j] < ranking[posMax])) oder ein stabiles Verfahren wie Bubblesort mit < verwenden. (1 Punkt)

e) Emre Aksoy fragt, warum die Vorschlagsliste aus a) im Programm sortiert wird – die Daten stammen doch ohnehin aus der Datenbank barcamp. Erläutere zwei Vorteile einer Sortierung mit ORDER BY in der Datenbankabfrage und eine Situation, in der die Sortierung im Programm sinnvoll oder nötig ist. (3 Punkte)

Vorteile von ORDER BY (je 1 Punkt, zwei verlangt):

Die Datenbank nutzt schnelle Sortierverfahren und ggf. Indizes; der eigene Code ist kürzer und weniger fehleranfällig.
Filtern (WHERE) und Sortieren geschehen zusammen, es werden nur die benötigten Datensätze in der richtigen Reihenfolge übertragen.
Die Reihenfolge ist für alle Anwendungen, die die Abfrage nutzen, einheitlich (z. B. auch mit Zweitkriterium ORDER BY punkte_schnitt DESC, abweichung).

Sortierung im Programm (1 Punkt, eine verlangt):

Die Daten kommen nicht (direkt) aus der Datenbank, z. B. über eine API, von einem Gerät oder aus einer Datei.
Das Kriterium wird erst im Programm berechnet oder von den Nutzenden gewählt (wechselnde Sortierung im Portal über eine Vergleichsfunktion), ohne die Daten neu abzufragen.
Die Liste ändert sich laufend im Speicher (Tagesplan mit spontanen Sessions), sodass sortiertes Einfügen günstiger ist als eine neue Abfrage.

Links und weitere Informationen

Hinweis zur Nachnutzung als Open Educational Resource (OER)

Dieser Artikel und seine Texte, Bilder, Grafiken, Code und sonstiger Inhalt sind - sofern nicht anders angegeben - lizenziert unter CC BY 4.0. Nennung gemäß TULLU-Regel bitte wie folgt: “Übungsaufgaben zu Sortieralgorithmen und Vergleichsfunktionen” von oer-informatik.de (H. Stein), Lizenz: CC BY 4.0. Der Artikel wurde unter https://oer-informatik.de/sortieralgorithmen-uebungsaufgaben veröffentlicht, die Quelltexte sind in weiterverarbeitbarer Form verfügbar im Repository unter https://gitlab.com/oer-informatik/algorithmik/algorithmen. Erstellt mit KI-Assistenz; von mir umfassend redaktionell überarbeitet, geprüft und freigegeben. Stand: 29.10.2026.

[Kommentare zum Artikel lesen, schreiben] / [Artikel teilen] / [gitlab-Issue zum Artikel schreiben]

Übungsaufgaben zu Sortieralgorithmen und Vergleichsfunktionen