Ausgabe 2003-03-13
Lutz Prechelt
1. Stellen
Sie aus der Erinnerung eine Liste der 5 häufigsten Arten von Programmierfehlern
auf, die Sie in der Vergangenheit gemacht haben.
·
Welche davon ließen sich leicht vermeiden? Wie?
·
Welche davon verursachen besonders hohen Aufwand, sie zu
finden?
2. Betrachten
Sie den Quelltext des ältesten nicht-trivialen Ihrer Java-Programme, das Sie
noch auftreiben können.
·
Finden Sie es gut lesbar?
·
Würde jemand anderes es gut lesbar finden?
·
Lesen Sie die Java-Kodierrichtlinien nach (siehe
Vorlesungs-Webseite) Wo haben Sie dagegen verstossen?
·
Welche der Verstöße sind erheblich, welche eher
unwichtig?
3. Implementieren
Sie das Sortierverfahren Quicksort für Felder von int-Werten in Java. Ihre
Methode muss die folgende Signatur haben:
static void quicksort(int a[], int low, int
high)
und sortiert nur den Teilbereich von (einschliesslich) Indexwert low bis
Indexwert high in dem Feld aufsteigend.
(Der normale Aufruf ist also quicksort (a, 0,
a.length-1))
·
Implementieren Sie mit Ihrem normalen Programmierstil und
Ihrer normalen Programmiermethodik
·
Testen Sie das Programm jedoch absolut NICHT. (Es sollte
lediglich sauber durch den Übersetzer laufen).
·
Es ist erwünscht, das das Programm Defekte enthält. Wir
werden es für spätere Übungen als Grundlage einsetzen.
·
Speichern Sie das Programm auf eine Diskette und nehmen
Sie diese zu den weiteren Vorlesungen mit.
·
Hier nochmal die Grundidee von Quicksort, falls Sie sich
daran nicht mehr erinnern können:
·
Wähle ein beliegiges Elelement des Sortierbereichs als
Aufteilwert (Pivot-Element)
·
Ordne dann in einem Durchgang alle Elemente des
Sortierbereichs so um, dass drei Bereiche entstehen:
-
LINKS enthält nur Werte die kleiner oder gleich dem
Pivot-Element sind
-
RECHTS enthält nur Werte die größer oder gleich dem
Pivot-Element sind
-
MITTE enthält nur das Pivot-Element
·
Sortiere dann rekursiv mittels Quicksort die Bereiche
LINKS und RECHTS
Es ist
wichtig, dass Sie diese Aufgabe bis zu Ende bearbeiten, denn sonst ist mehreren
späteren Übungen die Grundlage entzogen. Wenn Sie es heute nicht schaffen, tun
Sie es bitte morgen oder übermorgen.