Folge 8 - Sortierverfahren

Buch-Version

Die Folgen 1 bis 9 gibt es jetzt auch als Buch-Version. Noch nicht gedruckt, aber in Form von fünf PDF-Dateien. Die Buch-Version sieht besser aus und enthält Themen, die ich aus Zeitgründen im regulären Kurs nicht behandeln kann, zum Beispiel das komplette Kapitel 6 sowie einige Exkurse.
Es gibt eine ganze Reihe von Sortierverfahren, wobei die komplizierten meistens wesentlich schneller sind als die einfachen. Bei kleinen Zahlenmengen (unter 10.000) spielt der Geschwindigkeitsfaktor allerdings keine große Rolle, so dass wir zunächst einmal ein sehr einfaches Sortierverfahren behandeln wollen, den Bubblesort.

1. Bubblesort

Bubblesort ist das einfachste aller Sortierverfahren, es ist sehr einfach zu verstehen. Lesen Sie sich bitte jetzt die Theorieseite "Bubblesort" durch und kommen Sie dann an diese Stelle zurück.

Bubblesort

Übung 8.1 (4 Punkte)

Implementieren Sie für die Klasse Liste aus Folge 7 eine Methode

public void bubblesort()

welche die Zahlen der Liste nach dem Bubblesort-Verfahren sortiert, so wie es in dem Theorieteil "Bubblesort" beschrieben ist.


Übung 8.2 (4 Punkte)

Ein Sortierverfahren, welches sich stark an den Bubblesort anlehnt, ist der Shakersort.

Informieren Sie sich im Internet, was man unter dem Shakersort-Algorithmus versteht und implementieren Sie dann eine entsprechende Methode

public void shakersort()

für die Klasse Liste.


Experten-Übung 8.A (4 Punkte)

Implementieren Sie für die Klasse Liste eine rekursive Bubblesort-Methode!

In der Buch-Version dieses Kapitels finden Sie eine zweite Experten-Übung, in der Sie einen zweidimensionalen Array mithilfe des Bubblesorts sortieren müssen - erst waagerecht, dann senkrecht.

2. Selectionsort

Auch das Sortieren durch Auswählen ist ein einfaches Sortierverfahren, in seiner Geschwindigkeit ungefähr vergleichbar mit dem Bubblesort, welcher aber etwas einfacher zu programmieren ist.

Lesen Sie sich bitte die Theorieseite Selectionsort durch und kommen Sie dann bitte an diese Stelle zurück.

Übung 8.3 (4 Punkte)

Implementieren Sie für die Klasse Liste die beiden Methoden

public int miniPos(int ab)
public void selectionsort()

Die erste Methode liefert die Position der kleinsten Zahl in dem Array, wobei der Parameter ab bestimmt, ab wo überhaupt nach dem Miniumum gesucht werden soll.

Die zweite Methode implementiert den Selectionsort, wie er im Theorieteil beschrieben wurde.

Selectionsort

3. Insertionsort

Die dritte zu den einfachen Sortierverfahren gehörende Methode ist das Sortieren durch direktes Einfügen oder der Insertionsort. Bitte lesen Sie sich den Theorieteil hierzu durch. Er enthält auch ausführliche Implementationshinweise.

Übung 8.4 (4 Punkte)

Implementieren Sie für die Klasse Liste die Methode

public void insertionsort()

so wie im Theorieteil beschrieben!


Insertionsort

4. Praxis: Zeitverhalten der Algorithmen

In den Folgen 5 und 6 haben Sie gelernt, Java-Applets zu schreiben, und wenn Sie die letzte Übung der Folge 7 bearbeitet haben, sind Sie gut auf den nächsten Abschnitt vorbereitet, den ich wegen der Größe auf eine eigene Seite ausgelagert habe.

Übungen 8.5 - 8.8

Siehe Projekt Zeitverhalten von Sortieralgorithmen


Projekt: Zeitverhalten von Sortieralgorithmen

5. Theorie: Analyse des Zeitverhaltens

Nun wollen wir uns noch ein wenig mehr mit der Analyse des Zeitverhaltens beschäftigen. Lesen Sie sich dazu bitte den entsprechenden Theorieteil durch.

Übungen 8.9 - 8.11 (10 Punkte)

Siehe Theorieteil Analyse des Zeitverhaltens.

Analyse des Zeitverhaltens von Sortieralgorithmen

Völlig neu geschrieben für den Inf-Kurs von Herrn Brennemann am 21. Mai 2011!

Weiter mit...

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 3. Oktober 2006.


IMPRESSUM