Aufgabe 1: Elemente tauschen
Mit dem Bubble-Sort Algorithmus können Listen der Größe nach sortiert werden. Ein entscheidender Schritt des Algorithmus ist der Tausch von benachbarten Elementen in einer Liste.
Aufgabe:
Implementiere eine Methode „vertausche“, mit der zwei Elemente in einer Liste getauscht werden. Als Parameter sollen die Indizes der beiden Elemente übergeben werden, die getauscht werden sollen und die Liste, auf die das angewandt wird.
Tipps:
Nutze eine Hilfsvariable, um die beiden Werte zu tauschen. In dieser muss einer der Werte zwischengespeichert werden.
Aufgabe 2: Bedingung für den Tausch formulieren
Die beiden Elemente in der Liste sollen nur dann getauscht werden, wenn das vordere in der Liste größer ist als das nachfolgende Element.
Aufgabe:
Formuliere eine Bedingung, die den Tausch des ersten und des zweiten Elements der Liste nur durchführt, wenn das erste Element größer ist als zweite.
Tipps:
Überlege, welcher Operator der richtige ist: <, >, >=, <=.
Aufgabe 3: Die ganze Liste durchlaufen
Nun sollen nicht nur das erste und zweite Element einer Liste miteinander verglichen werden, sondern nach und nach die ganze Liste durchlaufen werden.
Dazu ist eine Schleife nötig.
Aufgabe:
Ergänze den Code um eine Schleife, sodass die ganze Liste durchlaufen wird und am Ende das größte Element ganz unten in der Liste steht.
Tipps:
Nutze die Laufvariable i wie den Index der Liste.
Zähle 1 dazu, um das nachfolgende Element in der Liste auszuwählen.
Aufgabe 4: Solange durch die Liste laufen, bis sie ganz sortiert ist
Meistens ist eine Liste nach einem Durchlauf nicht komplett sortiert. Man muss die Liste also öfter durchlaufen, damit die Anordnung der Elemente aufsteigend ist.
Überlege, wie häufig man die Liste durchlaufen muss, um sicher zu sein, dass sie korrekt sortiert ist.
Aufgabe:
Ergänze den Code um eine weitere Schleife, sodass das Aufsteigen des größten Elements so oft wiederholt wird, bis die Liste komplett sortiert ist.
Tipps:
Du musst eine Laufvariable mit einem anderen Namen nutzen. Meistens verwendet man j.
Zusatzaufgabe: Optimieren
Ein wesentliches Qualitätsmerkmal eines Computerprogramms ist die Geschwindigkeit, in der eine Aufgabe abgearbeitet wird (der Informatiker nennt das die Laufzeit eines Programms).
Häufig sollen Listen mit mehreren Tausend Elementen sortiert werden. Hierbei ist es entscheidend, unnötige Berechnungen zu vermeiden.
Unsere bisheriger Code durchläuft die Schleifen häufiger als es nötig wäre. Nutze die Schritt-für-Schritt Ausführung, um herauszufinden, wie oft ein Durchlaufen der Schleifen nötig ist.
Es kommt häufig vor, dass Listen bereits zufällig so vorsortiert sind, dass sie nicht so oft durchlaufen werden müssen, wie sie lang sind. Man kann also den Sortieralgorithmus vorher abbrechen. Dazu nutzt man die Variable „getauscht“, die den Wert wahr oder falsch annehmen kann. Wenn bei einem Durchlauf kein Tauschvorgang stattgefunden hat (getauscht = false), kann der Algorithmus beendet werden.
Aufgabe:
- Reduziere den Durchlauf der Schleifen auf die mindestens nötige Anzahl.
- Ergänze die Variable getauscht an passender Stelle, um den Algorithmus, zu beenden, wenn kein Tauschvorgang stattgefunden hat.
Tipps: