Visualisierung der Sortieralgorithmen Bubblesort, Insertionsort und

Transcrição

Lehrveranstaltung „Systemprogrammierung“
Prof. Dr. Groß, Prof. Dr. Heinzel
WS 2007/2008
Visualisierung der
Sortieralgorithmen
Bubblesort, Insertionsort und
Selectionsort
Name
Vorname
McLaughlin Lisa
Wäldchen
Lisa
Lehrveranstaltung „Graphik-Programmierung“
Visualisierung von Sortieralgorithmen
Inhaltsverzeichnis
Abbildungsverzeichnis _________________________________ 4
1. Projektbeschreibung (LM, LW) _________________________ 5
1.1 Thema_______________________________________________ 5
1.2 Ziel _________________________________________________ 5
1.3 Zielgruppe ___________________________________________ 6
1.4 Beschreibung der verwendeten Algorithmen _________________ 6
2. Anwendungsdokumentation ___________________________ 7
2.1 Kompilieren und Ausführen (LM) __________________________ 7
2.1.1. Systemvoraussetzungen ______________________________________ 7
2.1.2. Kompilieren und Ausführen ____________________________________ 7
2.2 Bedienung ___________________________________________ 7
2.2.1 Startfenster (LW) _____________________________________________ 8
2.2.2 AuswahlAlgorithmen (LW) _____________________________________ 8
2.2.3 Hauptfenster (LM) ____________________________________________ 9
2.2.3.1 Tab1 (LM) _______________________________________________ 10
2.2.3.2 Tab2 (LW)_______________________________________________ 12
2.2.3.3 Tab3 (LW)_______________________________________________ 14
3. Entwicklungsdokumentation__________________________ 16
3.1 Überblick (LW, LM) ____________________________________ 16
3.2 Programmierung der Algorithmen (LW, LM) ________________ 19
3.3 Programmierung des Paketes GUI ________________________ 20
3.3.1 Startfenster (LW) ____________________________________________ 20
3.3.2 AuswahlAlgorithmen (LW) ____________________________________ 20
3.3.3 Hauptfenster (LM, LW) _______________________________________ 21
3.3.3.1 Menü (LM) ______________________________________________ 22
3.3.3.2 Tab1 (LM, LW) ___________________________________________ 22
3.3.3.3 Tab2 (LW)_______________________________________________ 23
3.3.3.4 Tab3 (LW)_______________________________________________ 23
3.3.4 Saeule (LM) _________________________________________________ 24
3.4 Programmierung des Paketes Berechnungen (LW) ___________ 25
3.4.1 Tab2 _______________________________________________________ 25
3.4.2 Tab3 _______________________________________________________ 26
3.5 Programmierung des Paketes Steuerung
(LW, LM) __________ 26
3.5.1 MAIN _______________________________________________________ 26
3.6 Programmierung des Paketes Utilities _____________________ 27
3.6.1
3.6.2
3.6.3
3.6.4
3.6.5
Erklaerungen (LW) ___________________________________________ 27
GeschwindigkeitsEinstellung (LW) _____________________________ 27
Menuefenster (LM, LW) _______________________________________ 28
RandomArray (LM, LW) _______________________________________ 28
Zeitmessung (LW) ___________________________________________ 29
4. eingesetzte Werkzeuge und Basisliteratur (LW, LM) _______ 29
5. Darstellung relevanter Probleme und deren Lösung (LM, LW) 30
6. Darstellung des Aufwandes (LW, LM) ___________________ 32
Erstellt von Lisa McLaughlin und Lisa Wäldchen
Seite 2 von 35
7. Fazit (LM, LW)_____________________________________ 33
8. Quellen __________________________________________ 34
Die einzelnen Kapitel sind mit den Initialen der Verfasser gekennzeichnet.
Lisa McLaughlin LM
Lisa Wäldchen LW
Generell ist anzumerken, dass einige Kapitel, das heißt auch einige
Klassen im Programm zusammen entwickelt wurden, aus diesem Grund
sind dann beide Initialen zu lesen.
Genaue Informationen, wer was bearbeitet hat, sind der JavaDokumentation zu entnehmen.
Seite 3 von 35
Abbildungsverzeichnis
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
Abbildung
1 - Startfenster _________________________________________________ 8
2 - AuswahlAlgorithmen __________________________________________ 8
3 - Tab Graphische Erklaerung ____________________________________ 10
4 - Tab "Zeitliche Berechnung"____________________________________ 12
5 - Fehler bei der Menge 1 _______________________________________ 12
6 - Fehlermeldung bei der Menge 2 ________________________________ 13
7 - Hilfefenster auf Tab2_________________________________________ 14
8 - Tab "Vergleich" _____________________________________________ 14
9 - Paket Algorithmen___________________________________________ 17
10 - Paket GUI ________________________________________________ 17
11 - Paket Berechnungen ________________________________________ 18
12 - Paket Steuerung ___________________________________________ 18
13 - Packet Utilities_____________________________________________ 18
15 - Klasse Startfenster _________________________________________ 20
16 - Klasse AuswahlAlgorithmen __________________________________ 20
17 - Singleton _________________________________________________ 21
18 - Klasse Saeule _____________________________________________ 24
19 - Klasse Tab2_______________________________________________ 25
20 - Klasse Tab3_______________________________________________ 26
21 - Klasse MAIN ______________________________________________ 26
22 - Klasse Erklaerungen ________________________________________ 27
23 - Klasse GeschwindigkeitsEinstellungen __________________________ 27
24 - Klasse MenueFenster _______________________________________ 28
25 - Klasse RandomArray ________________________________________ 28
26 - Klasse Zeitmessung ________________________________________ 29
Seite 4 von 35
1. Projektbeschreibung (LM, LW)
1.1 Thema
Im Rahmen der Ausarbeitung für das Fach Systemprogrammierung im
Wintersemester 2007 / 2008 haben wir uns für das Thema Visualisierung der
Sortieralgorithmen Bubblesort, Insertionsort und Selectionsort entschieden.
Die Funktionsweisen der verschiedenen Sortieralgorithmen wurden uns im 1.
Semester von Herrn Prof. Dr. Ehrenberger in dem Fach Algorithmen und
Datenstrukturen näher gebracht.
Wir haben uns für dieses Thema entschieden, da wir aus eigener Erfahrung
gemerkt haben, dass es schwierig sein kann, die Funktionsweise der
verschiedenen Sortieralgorithmen nur anhand des vorgegebenen Pseudocodes zu
verstehen.
Im Rahmen des Projektantrages wurde die Aufteilung wie folgt festgelegt:
Lisa McLaughlin
Visualisierung des Sortieralgorithmen anhand von Säulen
Paralleler Ablauf von Pseudocode
Umsetzung des Sortieralgorithmus Selectionsort
Lisa Wäldchen
Visualisierung der Oberfläche und Tabs
Zeitliche Berechnung der Sortierverfahren (Tab2)
Implementieren des Bubblesort- und des Insertionsort-Algorithmus
1.2 Ziel
Mit dieser Anwendung soll zunächst die Sortierung von einem Feld von
Zufallszahlen mit fester Größe durch die jeweilige Funktionsweise der drei
Algorithmen visualisiert werden.
Zudem soll es dem Nutzer auch möglich sein, eine Menge anzugeben, die der
Größe des zu sortierenden Feldes entspricht. Er soll dann Informationen über die
Dauer der Sortierung und die Anzahl an Vergleichen *I und Austauschen*²
innerhalb der Sortierung erhalten.
*I = Wie oft wurde eine Zahl mit einer anderen Zahl aus dem Feld verglichen?
*² = Wie oft wurde eine Zahl mit einer anderen Zahl aus dem Feld getauscht?
Seite 5 von 35
1.3 Zielgruppe
Generell soll die fertige Anwendung primär zum besseren Verständnis der
Funktionsweisen der Sortieralgorithmen dienen.
Dadurch, dass wir versuchen wollen, die Erklärungen so einfach wie möglich zu
gestalten, ist es für jeden gedacht, der sich für das Thema interessiert.
Natürlich soll es auch hilfreich für die Studenten sein, da, wie bereits erwähnt,
Herr Ehrenberger unter anderem diese Sortieralgorithmen in seinem Unterricht
durchnimmt. Unser Programm soll sie von daher beim Lernen unterstützen.
Außerdem kann es auch dem Professor zu Demonstrationszwecken dienen.
1.4 Beschreibung der verwendeten Algorithmen
Im Folgenden werden kurz die verwendeten Algorithmen erklärt, damit ein
Eindruck entsteht, was genau bei den Sortiervorgängen passiert.
Bubblesort
„Der Algorithmus vergleicht der Reihe nach zwei benachbarte Elemente und
vertauscht sie, falls sie in der falschen Reihenfolge vorliegen. Dieser
Vorgang wird solange wiederholt, bis keine Vertauschungen mehr nötig sind.
Hierzu sind in der Regel mehrere Durchläufe erforderlich.“
Insertionsort
„Der Algorithmus entnimmt der unsortierten Eingabefolge ein beliebiges
(z.B. das erste) Element und fügt es an richtiger Stelle in die (anfangs
leere) Ausgabefolge ein.“ Hier werden alle größeren Elemente als das
aktuelle nach hinten geschoben, bis dies nicht mehr möglich ist.
Selectionsort
„Sei S der sortierte Teil des Arrays und U der unsortierte Teil. Am Anfang ist
S noch leer, U entspricht dem ganzen Array. Das Sortieren durch Auswählen
funktioniert so:
Suche das kleinste Element in U und vertausche es mit dem ersten Element.
Danach ist das Array bis zu dieser Position sortiert. S ist um ein Element
gewachsen, U um ein Element kürzer geworden. Anschließend wird das
Verfahren solange wiederholt, bis das gesamte Array abgearbeitet worden
ist.“
Zitate: [Quelle 1]
Seite 6 von 35
2. Anwendungsdokumentation
2.1 Kompilieren und Ausführen (LM)
2.1.1. Systemvoraussetzungen
Um das Programm ausführen zu können, muss eine Java Laufzeitumgebung
installiert sein.
2.1.2. Kompilieren und Ausführen
Unter Windows
Um das Programm unter den einzelnen Betriebssystemen von Windows zu
starten, haben wir eine jar-Datei erstellt, die bei Benutzung die MAIN.java
ausführt (und somit das gesamte Programm startet).
Unter Solaris
Um das Programm unter dem Betriebssystem Solaris auszuführen, ist es
notwendig folgende Befehle einzugeben: javac MAIN.java. Dieser Befehl
kompiliert das Programm. Erfolgt die Kompilierung ohne Fehlermeldungen folgt
der Befehl: java MAIN. Durch diesen Befehl wird das Programm gestartet.
2.2 Bedienung
Das Programm ist so entwickelt worden, dass es zum größten Teil
selbsterklärend ist. Funktionen, die zusammen gehören wurde immer auf einen
Tab platziert. Für den Fall, dass Fragen zu dem Programm entstehen, wurde eine
Hilfe in der Menüleiste eingefügt.
Im Folgenden wird die Bedienung des gesamten Programms erläutert.
Seite 7 von 35
2.2.1 Startfenster (LW)
Abbildung 1 - Startfenster
Nachdem das Programm gestartet wird, erscheint als aller erstes ein kleines
Startfenster. Dieses dient dazu, einen ersten Eindruck zu vermitteln. Nach
unserer Definition sollte ein Startfenster mindestens ein Logo mit dem Namen
des Programms und die Namen der Programmierer enthalten und anzeigen.
Hierzu haben wir selbst ein Logo mit einem Slogan entworfen, bei dem man im
Hintergrund die Pseudocodes der jeweiligen Sortierverfahren erkennen kann. Bei
dem Programmnamen haben wir uns für sorty entschieden. Gesamt betrachtet
kann man sagen, dass das Logo mit dem dazu gehörigen Slogan den von uns
gewünschten ersten Eindruck „Mit Spaß Lernen“ vermittelt.
Die Dauer, wie lange das Startfenster angezeigt wird, haben wir auf 5 Sekunden
beschränkt.
2.2.2 AuswahlAlgorithmen (LW)
Abbildung 2 - AuswahlAlgorithmen
Seite 8 von 35
Nach dem Startfenster wird automatisch das Auswahlfenster angezeigt. In
diesem Fenster kann man sich nun entscheiden, über welches Sortierverfahren
man sich näher informieren möchte. Aus diesem Grund stehen einem drei
Buttons zur Verfügung, da in unserem Programm die Arbeitsweisen von drei
Sortierverfahren erklärt werden.
Dieses Fenster ist sehr übersichtlich und bietet noch keine Hilfen.
Durch Betätigen eines Buttons gelangt man zu dem dementsprechenden
Hauptfenster.
2.2.3 Hauptfenster (LM)
Das Hauptfenster ist in drei Tabs unterteilt. Jeder Tab beinhaltet eine andere
Funktion, die im Anschluss näher erläutert werden.
Im oberen Bereich befindet sich die Menüleiste. Unter dieser Menüleiste sind drei
Punkte zu finden: Menue, Algorithmen und Hilfe. Unter dem Punkt Menue hat
man die Möglichkeit, zurück in das Auswahlfenster zu gelangen, um einen
anderen Sortieralgorithmus auszuwählen oder das Programm zu beenden. Unter
dem Punkt Algorithmen werden die einzelnen Sortieralgorithmen aufgelistet und
beschrieben. Im Punkt Hilfe gibt es verschiedene Hilfepunkte, die helfen sollen,
das Programm zu verstehen. Zusätzlich gibt es hier weitere Informationen über
das Programm und dessen Hintergrund.
Seite 9 von 35
2.2.3.1 Tab1 (LM)
Auf dem ersten Tab „Graphische Erklärung“ wird der Sortiervorgang visuell
dargestellt. Um es besonders umfangreich darzustellen gibt es drei
Hauptbereiche, in dem die Visualisierung stattfindet.
Abbildung 3 - Tab Graphische Erklaerung
Punkt 1
Hier findet die bildliche Darstellung der Zahlen statt, die sortiert werden. Die
Zahlen sind zufällig gewählt und werden während dem Sortiervorgang markiert
und getauscht, damit der Ablauf des Algorithmus deutlich wird.
Punkt 2
In diesem Teil ist der Pseudocode des ausgewählten Sortieralgorithmus zu sehen.
Hier werden die Zeilen markiert, die während dem Sortiervorgang abgearbeitet
werden.
Punkt 3
Hier werden schriftliche Erklärungen zu dem Ablauf des Algorithmus gezeigt, die
den Sortiervorgang beschreiben. Zu jeder Zeile Code gibt es eine Erklärung, die
verdeutlichen soll, was genau geschieht und warum.
Alle drei Bereiche laufen parallel zueinander ab, sodass eine umfangreiche
Erklärung des Programms stattfindet.
Punkt 4
Durch das klicken des Buttons Sortiere wird der Sortierprozess gestartet und die
Visualisierung findet statt.
Seite 10 von 35
Punkt 5
Der Button Pause ermöglicht es dem Anwender, den Prozess zu pausieren.
Dadurch hat man Zeit, die Erklärungen zu lesen und sich den Code genauer
anzusehen. Durch erneutes klicken des Buttons wird der Sortiervorgang wieder
aufgenommen.
Punkt 6
Durch den Button Stop wird der Sortiervorgang abgebrochen. Es können dann
neue Zufallszahlen erzeugt oder ein anderer Sortieralgorithmus auswählt werden.
Punkt 7
Mit dem Button neue Randomzahlen kann eine neue Menge von Zufallszahlen
erzeugt und angezeigt werden, die dann sortiert werden können.
Punkt 8
Der Slider dient dazu, die Schnelligkeit des Sortiervorgangs zu bestimmen. Dies
muss eingestellt werden, bevor das Sortieren gestartet wird. Während dem
Sortieren kann die Geschwindigkeit nicht geändert werden, da man ja immer die
Möglichkeit hat, die Sortierung abzubrechen und die Geschwindigkeit zu ändern.
Punkt 9
Der Button Beenden in der rechten unteren Hälfte beendet das gesamte
Programm und schließt das Fenster.
Seite 11 von 35
2.2.3.2 Tab2 (LW)
Im zweiten Tab hat man nun die Möglichkeit, je nach Sortierverfahren eine
zeitliche Berechnung durchzuführen. In diesem Fall nutzen wir jetzt den
Bubblesort-Algorithmus. In den folgenden Schritten wird erklärt, was man auf
diesem Tab für Möglichkeiten hat und welche Informationen genau angezeigt
werden.
1
2
3
4
5
8
6
7
9
Abbildung 4 - Tab "Zeitliche Berechnung"
Punkt 1
Zunächst kann man bei diesem Punkt feststellen, dass man sich auf dem Tab
Zeitliche Berechnung befindet.
Punkt 2
Hier hat der Nutzer nun die Möglichkeit, eine Menge zwischen 1 und 200.000
einzugeben. Diese Zahl beschreibt die Größe des zu sortierenden Arrays. Dieses
Array wird dann mit Zufallszahlen erstellt, die zwischen 1 und der angegebenen
Zahl sein können.
Diese Menge wurde beschränkt, da bei größeren Zahlen die Sortierung zu lange
dauert und die Sortierung nicht abgebrochen werden kann. 200.000 dauert
schon sehr lange, wir wollten aber dem Nutzer nicht die Möglichkeit nehmen,
eine hohe Zahlenmenge zu testen. Wenn man eine Zahl außerhalb des
festgelegten Bereiches eingibt, erscheint folgendes Fenster:
Abbildung 5 - Fehler bei der Menge 1
Seite 12 von 35
Für den Fall, dass bei der Zeit 0 Millisekunden das Ergebnis ist, sollte man
einfach höhere Zahlen ausprobieren. Durch verschiedene Tests haben wir
herausgefunden, dass sich Zahlen zwischen 2000 und 8000 am Besten zum
Ausprobieren eignen.
Für den Fall, dass man eine falsche Eingabe tätigt, wie zum Beispiel Buchstaben,
oder das man gar keine Eingabe macht, wird folgendes Fenster angezeigt:
Abbildung 6 - Fehlermeldung bei der Menge 2
Punkt 3
Mit dem Button „Sortiere…“ startet man die Sortierung mit dem jeweiligen
Sortierverfahren.
Punkt 4
In diesem Fenster wird die Zeit / Dauer angezeigt, die der Sortieralgorithmus für
den Sortiervorgang benötigt. Diese Angabe wird in Millisekunden angegeben.
Diese Dauer in Sekunden anzuzeigen, wäre nicht ratsam gewesen, da die
Sortierung meist nicht sehr lange dauert und man so genauere Angaben erhält.
Punkt 5
Bei der Sortierung eines Feldes werden nacheinander nach verschiedenen
Algorithmen zwei Elemente miteinander verglichen. In diesem Feld wird nun die
Anzahl angezeigt, wie oft insgesamt bei einer Sortierung zwei Elemente
miteinander verglichen wurden.
Punkt 6
Die Anzeige in diesem Fenster entspricht der Anzahl, wie oft bei der gesamten
Sortierung zwei Elemente miteinander vertauscht wurden. Je nach
Sortierverfahren gibt es unterschiedliche Regeln, wann zwei Elemente getauscht
werden sollen. Beim Bubblesort werden sie sofort getauscht, wenn das erste
Element größer als das zweite ist und beim Selectionsort zum Beispiel wird erst
das gesamte Feld durchsucht, und dann wird getauscht.
Auf jeden Fall wird in diesem Feld die Anzahl angegeben, wie oft zwei Elemente
miteinander getauscht wurden.
Punkt 7
Dieser Button soll dazu dienen, nach einer Sortierung den Inhalt folgender Felder
zu leeren:
Das Feld, indem
der Nutzer die Menge angeben kann.
die Dauer angezeigt wird.
die Anzahl an Vergleichen angezeigt wird.
die Anzahl an Austauschen angezeigt wird.
Dies soll grundsätzlich der Übersicht dienen, denn wenn man die Werte nach der
ersten Sortierung stehen lässt und dann eine größere Menge angibt, dass heißt,
Seite 13 von 35
die Sortierung länger dauert, kann es dazu führen, dass der Nutzer verwirrt ist,
da die Zahlen von der alten Sortierung noch angezeigt werden.
Punkt 8
Die Buttons mit den Fragezeichen sollen dem Nutzer als Hilfe dienen, wenn er bei
den Feldern Menge, Anzahl der Vergleiche und Anzahl der Austausche fragen hat.
Beim Klicken erscheint ein neues Fenster, in dem eine kurze Erklärung zu dem
jeweiligen Punkt zu lesen ist. Im Folgenden ist eins von den drei Hilfefensters zu
sehen.
Abbildung 7 - Hilfefenster auf Tab2
Punkt 9
Dieser Button dient dazu, das Programm zu beenden.
2.2.3.3 Tab3 (LW)
1
2
8
3
4
5
6
7
9
Abbildung 8 - Tab "Vergleich"
Seite 14 von 35
Punkt 1
Diese Anzeige gibt dem Nutzer an, dass er sich bei dem Tab „Vergleich“ befindet,
mit dem eine Menge eingeben kann, die mit allen drei Sortierverfahren sortiert
wird und anschließend die Dauer der Sortierung angezeigt wird.
Punkt 2
Hier hat der Nutzer nun die Möglichkeit, eine Menge zwischen 1 und 200.000
einzugeben. Diese Zahl beschreibt die Größe des zu sortierenden Arrays. Dieses
Array wird dann mit Zufallszahlen erstellt, die zwischen 1 und der angegebenen
Zahl sein können.
Diese Menge wurde beschränkt, da bei größeren Zahlen die Sortierung zu lange
dauert und die Sortierung nicht abgebrochen werden kann. 200.000 dauert
schon sehr lange, wir wollten aber dem Nutzer nicht die Möglichkeit nehmen,
eine hohe Zahlenmenge zu testen. Wenn man eine Zahl außerhalb des
festgelegten Bereiches eingibt, erscheint ein Fenster, das den Nutzer darauf
aufmerksam macht, dass Zahlen zwischen 1 und 200.000 möglich sind. Ein
Beispiel für das Fenster ist unter dem Punkt 2.2.3.2 Tab „Zeitliche Berechnung“
zu sehen.
Für den Fall, dass bei der Zeit 0 Millisekunden das Ergebnis ist, sollte man
einfach höhere Zahlen ausprobieren. Durch verschiedene Tests haben wir
herausgefunden, dass sich Zahlen zwischen 2000 und 8000 am Besten zum
Ausprobieren eignen.
Für den Fall, dass man eine falsche Eingabe tätigt, wie zum Beispiel Buchstaben,
erscheint ein Fenster, dass dem Nutzer anzeigt, was er eingeben kann. Ein
Beispiel für das Fenster ist im Punkt 2.2.3.2 Tab „Zeitliche Berechnung“ zu
sehen.
Punkt 3
Mit dem Button „Sortiere…“ startet man die Sortierung mit dem jeweiligen
Sortierverfahren.
Punkt 4
In diesem Textfeld wird die Zeit / Dauer angezeigt, die der Sortieralgorithmus für
den Sortiervorgang mit dem Sortierverfahren Bubblesort benötigt.
Punkt 5
Hier wird angezeigt, wie lange die Sortierung mit dem Sortierverfahren
Insertionsort gedauert hat.
Punkt 6
Dieses Textfeld repräsentiert die Dauer der Sortierung mit dem Sortierverfahren
Selectionsort.
Punkt 4 bis 6
Diese Angaben werden in Millisekunden angegeben. Diese Dauer in Sekunden
anzuzeigen, wäre nicht ratsam gewesen, da die Sortierung meist nicht sehr lange
dauert und man so genauere Angaben erhält.
Durch mehrere Tests haben wir herausgefunden, dass der Insertionsort mit
seiner Funktionsweise jeweils am schnellsten sortiert und der Selectionsort
ungefähr doppelt so lange braucht.
Seite 15 von 35
Der Bubblesort benötigt durch seine Art und Weise ein Vielfaches mehr Zeit als
die anderen beiden Sortierverfahren.
Punkt 7
Dieser Button soll dazu dienen, nach einer Sortierung den Inhalt folgender Felder
zu leeren:
Das Feld, indem
der Nutzer die Menge angeben kann.
die Dauer der Sortierung mit dem Bubblesort angezeigt wird.
die Dauer der Sortierung mit dem Insertionsort angezeigt wird.
die Dauer der Sortierung mit dem Selectionsort angezeigt wird.
Dies soll grundsätzlich der Übersicht dienen, denn wenn man die Werte nach der
ersten Sortierung stehen lässt und dann eine größere Menge angibt, dass heißt,
die Sortierung länger dauert, kann es dazu führen, dass der Nutzer verwirrt ist,
da die Zahlen von der alten Sortierung noch angezeigt werden.
Punkt 8
Der Button mit dem Fragezeichen soll dem Nutzer als Hilfe dienen, wenn er bei
dem Feld Menge fragen hat. Beim Klicken erscheint ein neues Fenster, in dem
eine kurze Erklärung zu lesen ist. Ein Beispiel des Hilfefensters kann man unter
Punkt 2.2.3.2 Tab „Zeitliche Berechnung“ sehen.
Punkt 9
Dieser Button dient dazu, das Programm zu beenden.
3. Entwicklungsdokumentation
3.1 Überblick (LW, LM)
Das Programm „sorty“ verwendet bei der Hierarchie zur Übersicht zunächst
Pakete, die dann die einzelnen dazugehörigen Klassen beinhalten. Diese
Hierarchie ist im Folgenden beschrieben.
Seite 16 von 35
Zunächst gibt es das Paket Algorithmen, indem folgende Klassen enthalten sind:
Abbildung 9 - Paket Algorithmen
Des Weiteren existiert das Paket GUI mit folgenden Klassen:
Abbildung 10 - Paket GUI
Die Berechnungen innerhalb des zweiten und dritten Tabs haben wir in das Paket
Berechnungen ausgelagert. Dieses Paket sieht wie folgt aus:
Seite 17 von 35
Abbildung 11 - Paket Berechnungen
Da die Main-Klasse die wichtigste Klasse für das Programm ist, haben wir uns
dazu entschlossen, ein Packet Steuerung einzuführen, in dem diese Klasse
untergebracht ist.
Abbildung 12 - Paket Steuerung
Für alle Hilfsklassen haben wir ein extra Paket erstellt, das wir mit dem Namen
Utilities versehen haben. Darin sind folgende Klassen vorzufinden:
Abbildung 13 - Packet Utilities
Seite 18 von 35
In den folgenden Punkten wird auf die einzelnen Pakete und deren Klassen näher
eingegangen. Detaillierte Informationen sind der Java-Dokumentation oder dem
Quellcode im Anhang zu entnehmen.
3.2 Programmierung der Algorithmen (LW, LM)
Zunächst haben wir uns bei der Programmierung der Algorithmen an das Skript
von Herrn Prof. Dr. Ehrenberger [Quelle 2] gehalten. In seinem Skript
Algorithmen und Datenstrukturen sind der Insertionsort und der Selectionsort so
beschrieben, dass wir den Code einfach umsetzen konnten. Beim Bubblesort
jedoch haben wir uns Anregungen von einer Internetseite [Quelle 3] geholt und
dementsprechend angepasst und umgesetzt.
Abbildung 14 – Klassen BubbleSort, InsertionSort und SelectionSort
Diese Klassen führen eine Sortierung von einem Zahlenarray durch, der von der
Hauptklasse übergeben wird. Die Zahlenmenge wird je nachdem mittels dem
Bubblesort-, Insertionsort- oder Selectionsort-Algorithmus sortiert. Der
Sortiervorgang kann in zwei Varianten gestartet werden.
Um die zeitliche Berechnung durchzuführen (Tab2) werden jeweils die Methoden
startBubbleOhneVis(), startInsertionOhneVis() oder startSelectionOhneVis()
verwendet. Dabei wird die Zeit gestoppt, die der Algorithmus benötigt, um das
Array zu sortieren und zusätzlich noch wie oft Zahlen verglichen und getauscht
werden.
Die zweite Variante ermöglicht das Visualisieren des Sortiervorgangs. Dazu wird
jeweils ein zusätzlicher Thread gestartet, die dann, mittels der Referenz auf das
Objekt der Klasse Hauptfenster.java, Methoden aus dem Hauptfenster aufrufen.
Dadurch wird der Sortiervorgang für den Anwender sichtbar.
Seite 19 von 35
3.3 Programmierung des Paketes GUI
3.3.1 Startfenster (LW)
Abbildung 15 - Klasse Startfenster
Diese Klasse erstellt für eine von der Main-Klasse übergebene Zeit ein Fenster,
welches als Einleitung für das Programm dienen soll. Hierzu wird von der MAIN
der Konstruktor aufgerufen. Darin wird die Methode startBildZeigen() aufgerufen,
die dann das Fenster erstellt (Größe, Rand,…) Hierbei werden ein Bild, der
Programmname und das Label mit den Namen der Programmierer hinzugefügt.
Nach Ablauf der übergebenen Zeit wird das Startfenster ausgeblendet und das
Fenster mit der Auswahl der Algorithmen erscheint.
3.3.2 AuswahlAlgorithmen (LW)
Abbildung 16 - Klasse AuswahlAlgorithmen
Das Auswahlfenster erscheint nach dem Startfenster und stellt drei Buttons zur
Verfügung. Mit diesen drei Buttons kann man sich für einen Sortieralgorithmus
entscheiden. Das Startfenster startet den Konstruktor, der das Fenster erstellt
(Größe, …) und auch die Buttons. Diese werden dann mit dem Label, auf dem die
Schrift zu finden ist, auf das Panel gesetzt und dann dem Frame (Fenster)
hinzugefügt. Wenn man einen der Buttons gedrückt, wird im ActionListener
zunächst unterschieden, um welchen Button / Algorithmus es sich handelt. Dann
wird das jeweilige Hauptfenster erstellt Dies geschieht mit Hilfe der
Hauptfenster-Instanz (Singleton), die im Folgenden noch näher beschrieben
wird.
Seite 20 von 35
3.3.3 Hauptfenster (LM, LW)
Graphik siehe Anhang
In der Klasse Hauptfenster.java wird die eigentliche Graphische Oberfläche des
Programms erzeugt und zusammengestellt. Es werden drei Tabs und eine
Menüleiste, alles Buttons und der Slider erzeugt und auf ein Frame, an die
entsprechenden Stellen gesetzt.
Auf die verschiedenen Tabs und der Menüleiste wird im Anschluss genauer
eingegangen.
Die Methode getInstance() bringt folgende Funktion mit sich:
„Das Singleton ist ein in der Softwareentwicklung eingesetztes Entwurfsmuster
und gehört zur Kategorie der Erzeugungsmuster. Es verhindert, dass von einer
Klasse mehr als ein Objekt erzeugt werden kann. Dieses Einzelstück ist darüber
hinaus üblicherweise global verfügbar.“ [Quelle 1]
Da mehrere Klassen, unter Anderem die einzelnen Sortierverfahren und einige
Utilitie-Klassen, Zugriff benötigen, haben wir uns dazu entschlossen, dieses
Muster anzuwenden. In der Dokumentation ist unter dem Punkt 5. Darstellung
relevanter Probleme und deren Lösung ein weiterer Grund beschrieben, warum
wir ein Singleton eingesetzt haben. Des Weiteren ist doch der Quellcode
angegeben.
Im Folgenden ist nun das UML-Diagramm von dem Singleton zu sehen:
Abbildung 17 - Singleton
Generell ist noch zu beachten, dass bei der Verwendung eines Singletons der
Konstruktor private sein sollte.
Nun steht das Objekt und damit auch alle Methoden der Klasse Hauptfenster
global mit folgendem Aufruf zur Verfügung:
Hauptfenster.getInstance(„“)
Nach dem Konstruktor folgen zunächst etliche Klassen, die dazu dienen, die
einzelnen Textfelder auf dem Hauptfenster mit Strings zu „beschreiben“. Diese
Methoden werden dann zum Beispiel von den Klassen des Paketes Algorithmen
oder Utilities genutzt und aufgerufen.
Nach diesen Methoden folgen einige, die für die visuelle Sortierung auf dem
ersten Tab dienen. Mit deren Hilfe werden die Säulen z.B. markiert oder die
Markierung wieder gelöscht.
Danach bis zum Ende der Klasse sind alle ActionListener aufzufinden, die für den
reibungslosen Ablauf nötig sind.
Seite 21 von 35
3.3.3.1 Menü (LM)
In der Menüleiste befinden sich die Punkte Menue, Algorithmen und Hilfe. Unter
dem Punkt Menue hat man die Möglichkeit in das Auswahlfenster zurück zu
gelangen. Dafür wird das Hauptfenster mit der Methode dispose() geschlossen
und ein neues Objekt der Klasse AuswahlAlgorithmen.java erzeugt. Des Weiteren
hat man unter dem Punkt Menue die Möglichkeit das Programm zu beenden.
Unter den Punkten Algorithmen und Hilfe wird jeweils ein Objekt der Klasse
Menuefenster.java erstellt. Diese Klasse erzeugt ein JFrame in dem jeweils der
entsprechende Text geladen wird. Es werden die einzelnen Sortieralgorithmen
erklärt, die das Programm verwendet und es gibt Informationen und Erklärungen
zu dem Programm.
3.3.3.2 Tab1 (LM, LW)
Auf dem ersten Tab Graphische Erklaerung wird der vorher ausgewählte
Sortieralgorithmus Visualisiert, indem eine Graphik, der Pseudocode des
Algorithmus und eine schriftliche Erklärung gezeigt werden. Diese Komponenten
laufen parallel zueinander ab.
Auf diesem Tab wurde ein JPanel gesetzt ohne LayoutManager, auf dem alle
Komponenten pixelgenau gesetzt werden.
In der linken oberen Hälfte wurde die Graphik platziert. Hier wird ein JPanel
erzeugt auf dem zunächst eine Menge von Zufallszahlen durch Säulen graphisch
dargestellt wird. Die Säulen werden durch die Klasse Saeule.java mittels der
Methode paintComponent() gezeichnet. Für jede Zahl wird ein Objekt dieser
Klasse mit einer bestimmten Größe, Position und Farbe erzeugt. Diese Parameter
wurden als statische Variablen festgelegt.
Während dem Sortiervorgang werden die Methoden zeichneRahmen() und
loescheSaeule() aufgerufen, um das Sortieren der Zahlen zu zeigen. Gesteuert
wird der Sortiervorgang mittels den Buttons Sortiere, Pause und Stop. Sortiere
startet den Sortiervorgang, indem der ActionListener sortiereButton() die
Methode
starteSortierenBubble(),
starteSortierenInsertion()
oder
starteSortiereSelection() aufruft.
Der Button Pause lässt den Sortiervorgang pausieren, solange bis dieser Button
erneut gedrückt wird. Er ruft die Methode pause() der jeweiligen
Algorithmusklasse auf.
Der Button Stop bricht den Sortiervorgang ab. Hierfür wird die Methode stop()
aufgerufen, die den Thread beendet.
Der Button neue Randomzahlen erzeugt eine neue Menge Zufallszahlen, die
gezeichnet werden und der Sortiervorgang kann erneut gestartet werden.
Der Slider dient dazu, die Geschwindigkeit der Sortierung festzulegen. Bevor die
Sortierung gestartet wird, kann die Geschwindigkeit mittels der Klasse
GeschwindigkeitsEinstellung.java verändert werden. Durch die Methode sleep()
in den Klassen Bubblesort.java, Insertionsort.java und Selectionsort.java wird die
Sortierung verzögert, damit die Visualisierung für den Anwender sichtbar wird.
In der rechten oberen Hälfte des Frames wird der Pseudocode des Algorithmus
gezeigt. Hierfür wird ein JTextArea erzeugt und der entsprechende Text hinein
gesetzt. Durch das Aufrufen der Methode zeileMarkieren() werden einzelnen
Zeilen mittels einem Highlighter markiert, um deutlich zu machen, welcher Teil
des Algorithmus zurzeit bearbeitet wird. Das Markieren der Zeilen und das
Zeichnen der Säulen läuft parallel zueinander ab.
Seite 22 von 35
In der linken unteren Hälfte des Frames wurde ein JTextArea gesetzt, um hier
eine schriftliche Erklärung zu zeigen. Dafür wird zu jeder Zeile des Pseudocodes
eine Erklärung in das JTextArea geschrieben. Die Erklärungen befindet sich in der
Klasse Erklaerungen.java und werden mittels der Methode setzeErklaerungen()
in das JTextArea geschrieben. Dies läuft ebenfalls parallel zu der Graphik und
dem Pseudocode ab, sodass eine rundum Erklärung des Algorithmus stattfindet.
3.3.3.3 Tab2 (LW)
Der zweite Tab trägt zunächst den Namen Zeitliche Berechnung. Dass bedeutet,
dass im Grunde hier die Dauer einer Sortierung mit dem jeweiligen
Sortierverfahren gemessen und angezeigt wird.
Generell wurde für diesen Tab kein Layoutmanager benutzt, sodass wir alle
Elemente Pixelgenau nach unseren Vorstellungen setzen konnten. Hier gibt es
nun insgesamt 4 Textfelder, in denen die Angaben der Sortierung angezeigt
werden, und 4 Labels, die jeweils eine kleine Beschreibung der Textfelder
enthalten. Die Textfelder wurden, bis auf das Feld „Menge“, auf nichtveränderbar gesetzt, da diese Felder nur zu Demonstrationszwecken dienen.
Des Weiteren sind auf diesem Tab 3 Hilfebuttons zu finden, die durch ein kleines
Fragezeichen gekennzeichnet sind. Diese werden jeweils den ActionListenern
hinzugefügt, die dann mit Hilfe der Klasse Menuefenster.java ein Menü-, bzw. ein
Hilfefenster erstellt.
Der Button „Sortiere…“ wird auch dem ActionListener hinzugefügt, der dann die
Berechnungen mit Hilfe der Klasse Tab2.java durchführt.
Der Button „Felder leeren“ wird ebenfalls dem ActionListener hinzugefügt, der die
4 zur Verfügung stehenden Textfelder mit leeren Strings füllt und so für den
Nutzer „leert“.
Auch der „Beenden“ Button wird dem ActionListener hinzugefügt, der dann das
gesamte Programm mit einem System.exit(0) beendet.
3.3.3.4 Tab3 (LW)
Der dritte Tab ähnelt stark dem zweiten Tab. Er trägt die Bezeichnung
„Vergleich“ und stellt daraus resultierend einen zeitlichen Vergleich zwischen den
3 Sortierverfahren dar.
Generell wird auch hier kein Layoutmanager genutzt. Insgesamt gibt es auch hier
4 Textfelder, in eines kann der Nutzer eingaben machen und durch die anderen
drei werden dem Nutzer Angaben zur Sortierung gemacht. Aus diesem Grund
sind diese drei Textfelder auf nicht-veränderbar gesetzt.
Es existieren auch 4 Labels, die Informationen zu den Textfeldern enthalten.
Ergänzend sind auch hier die Hilfebuttons mit den Fragezeichen zu finden, die
dem ActionListener hinzugefügt werden und dort dann mit Hilfe der Klasse
Menuefenster.java ein Hilfefenster erstellt wird.
Auf dem dritten Tab existiert auch ein Button „Sortiere…“ der dem ActionListener
hinzugefügt wird. Dieser startet dann mit Hilfe der Klasse Tab3.java die
Berechnungen.
Der Button „Felder leeren“ wird ebenfalls dem ActionListener hinzugefügt, der die
4 zur Verfügung stehenden Textfelder mit leeren Strings füllt und so für den
Nutzer „leert“.
Auch der „Beenden“ Button wird dem ActionListener hinzugefügt, der dann das
gesamte Programm mit einem System.exit(0) beendet.
Seite 23 von 35
3.3.4 Saeule (LM)
Abbildung 18 - Klasse Saeule
Die Klasse Saeule.java ist für das Zeichnen der einzelnen Säulen auf dem Tab1
zuständig. Jede Säule stellt ein Objekt der Klasse Saeule.java dar.
Beim erstellen eines Objektes dieser Klasse, wird die Methode paintComponent()
durch das System aufgerufen, in der ein Objekt vom Typ Graphics übergeben
wird, mit der eine Säulen gezeichnet wird.
Beim Starten des Programms erzeugt die Klasse Hauptfenster.java die Objekte
der Klasse Saeulen.java in der Methode zeichneFeld(). Nachdem ein Objekt
erstellt wurde, wird die Methode zeichneSaeule() aufgerufen, um die Parameter
für die Größe und Farbe dieser entsprechenden Zahl zu setzen. Dies wird so
lange wiederholt, bis alle 15 Zufallszahlen gezeichnet wurden.
Um die visuelle Sortierung der Säulen darzustellen, wird die Methode
rahmenZeichnen(boolean x) aufgerufen. Sie bestimmt, ob ein schwarzer Rahmen
um die Säule gezeichnet wird oder nicht, indem eine boolean-Variable auf true
oder false gesetzt wird.
Soll eine Säule gelöscht werden, z.B. bei dem Tauschvorgang, werden von der
Methode loescheSaeule() der Klasse Hauptfenster.java Parameter mit den
Werten 0 übergeben, sodass eine nicht-sichtbare Säule gezeichnet wird.
Seite 24 von 35
3.4 Programmierung des Paketes Berechnungen
(LW)
3.4.1 Tab2
Abbildung 19 - Klasse Tab2
Der zweite Tab dient zur zeitlichen Berechnung einer Sortierung. Die Klasse
besteht aus einer Methode, die für die gesamte Berechnung zuständig ist. Hierbei
wird zunächst die vom Nutzer eingegebene Menge ausgelesen und überprüft,
dass heißt, ob die Zahl zwischen 1 und 200.000 ist und ob es sich eventuell um
keine Zahl handelt. Danach wird ein Feld mit der Länge der ausgelesenen Menge
erstellt. Dieses Feld wird mit Hilfe der Klasse RandomArray.java mit Zufallszahlen
gefüllt. Im nächsten Schritt wird durch eine if-Anweisung unterschieden, um
welchen Sortieralgorithmus es sich handelt.
Danach wird das Feld mit Zufallszahlen an die jeweilige Methode der Algorithmen
übergeben
(startBubbleOhneVis(),
startInsertOhneVis()
und
startSelectionOhneVis() ). Nachdem die Sortierung durchgeführt wurde, wird die
Dauer der Sortierung durch die Methode gibDauer() der jeweiligen
Sortierverfahren abgerufen und mit Hilfe der Hauptfenster-Instanz durch die
Methode setzeZeit2Tab() in das Feld „Dauer der Sortierung in Millisekunden“
geschrieben.
Danach werden noch mit Hilfe der Methoden gibAnzVergleich() und
gibAnzAustausch() der jeweiligen Sortierverfahren die Anzahl, wie oft zwei
Elemente bei der Sortierung miteinander verglichen und getauscht wurden,
gesichert. Mit Hilfe der Hauptfenster-Instanz werden diese Zahlen durch die
Methoden setzeAnzVergleich() und setzeAnzAustausch() in die jeweiligen Felder
der GUI geschrieben.
Jeder mögliche Fehler der entstehen kann, wird abgefangen und dieser wird dem
Nutzer mit einem kleinen Popup-Fenster kenntlich gemacht.
Seite 25 von 35
3.4.2 Tab3
Abbildung 20 - Klasse Tab3
Der dritte Tab dient zunächst dem zeitlichen Vergleich der drei Sortierverfahren.
Der Aufruf der Methode erstelleBerechnung() erfolgt durch den ActionListener in
der Klasse Hauptfenster.java, wenn der Nutzer den Button „Sortiere…“ auf dem
dritten Tab gedrückt hat. Der Übergabewert Nachricht entspricht hierbei der
Eingabe, die der Nutzer getätigt hat, dass bedeutet, die Menge, wie groß das
Feld an Zufallszahlen werden soll.
Der erste Schritt ist es, zu schauen, ob es sich hierbei um eine Zahl handelt und
ob diese Zahl zwischen 1 und 200.000 liegt. Wenn mindestens eines davon nicht
der Fall ist, wird ein Popup-Fenster geöffnet, welches dem Nutzer sagt, was er
falsch gemacht hat und wie es richtig sein muss.
Danach wird mit Hilfe der Klasse RandomArray.java das Feld mit Zufallszahlen
erzeugt und danach in drei verschiedene int-Arrays, eines für jeden
Sortieralgorithmus, gespeichert.
Im nächsten Schritt werden nun die Sortierungen mit Hilfe der jeweiligen
Sortierklassen (BubbleSort.java, InsertionSort.java und SelectionSort.java)
durchgegangen und jeweils die Dauer der jeweiligen Sortierung geholt. Diese
Angaben werden jeweils mit Hilfe der speziellen Methoden der Hauptklasse in die
Textfelder geschrieben.
3.5 Programmierung des Paketes Steuerung
(LW, LM)
3.5.1 MAIN
Abbildung 21 - Klasse MAIN
Die MAIN-Klasse enthält die Variable Anzeigedauer, mit der festgelegt wird, wie
lange das Startfenster angezeigt werden soll. Standardgemäß haben wir diesen
Wert auf 5 Sekunden gesetzt, sodass der Nutzer genug Zeit hat, sich das
Startfenster anzuschauen. Wie man dem Namen der Klasse schon entnehmen
Seite 26 von 35
kann, enthält diese die main-Methode. Dort wird nun das Startfenster mit der
gegebenen Dauer gestartet.
3.6 Programmierung des Paketes Utilities
Diese Klassen sind Hilfsklassen und wurden als static definiert, sodass keine
Objekte mehr erzeugt werden müssen, sondern ein direkter Zugriff möglich ist.
3.6.1 Erklaerungen (LW)
Abbildung 22 - Klasse Erklaerungen
Diese Klasse wird von den Klassen der Sortierverfahren aufgerufen und somit
genutzt.
Die Methode überprüft zunächst mit einer if-Anweisung, um welches
Sortierverfahren es sich handelt. Im nächsten Schritt wird durch eine
switch/case-Abfrage überprüft, um welchen Wert es sich bei dem Übergabewert
parameter handelt. Je nachdem wird der Variable erkl ein String zugewiesen.
Dieser wird am Ende als Returnwert zurückgegeben.
Diese Strings entsprechen den jeweiligen Erklärungen auf dem ersten Tab,
parallel zur Sortierung.
3.6.2 GeschwindigkeitsEinstellung (LW)
Abbildung 23 - Klasse GeschwindigkeitsEinstellungen
Wenn der Nutzer auf dem Hauptfenster den Slider nutzt, um die Geschwindigkeit
der Sortierung einzustellen, übergibt die Klasse Hauptfenster.java diesen Wert an
diese Hilfsklasse.
Die Klasse GeschwindigkeitsEinstellung.java ermittelt nun durch eine ifAnweisung, um welchen Wert (zwischen 0 und 100) es sich bei dem
Übergabewert handelt. Je nachdem wird nun die Variable „schlafen“ gesetzt.
Hierbei ist anzumerken, dass 0 einer Geschwindigkeit von sehr schnell und 100
einer Geschwindigkeit von sehr langsam entspricht.
Wenn nun die Sortierung beginnt, holt sich der jeweilige Sortieralgorithmus den
Wert der Variable „schlafen“ mit Hilfe der Methode gibSchlafen().
Seite 27 von 35
3.6.3 Menuefenster (LM, LW)
Abbildung 24 - Klasse MenueFenster
Ein Objekt dieser Klasse wird jedes Mal erzeugt, sobald der Anwender in der
Menüleiste einen der Unterpunkte von Algorithmus oder Hilfe auswählt. Durch
den Aufruf der Methode erstelleHilfeFrame(String buttonFunk) der Klasse
Menuefenster.java wird ein JFrame mit einem JTextArea erzeugt, in dem ein
entsprechender Text geschrieben wird. Der Parameter buttonFunk gibt an,
welcher Text für das Fenster benötigt wird.
3.6.4 RandomArray (LM, LW)
Abbildung 25 - Klasse RandomArray
Diese Klasse wird generell genutzt, um ein Array mit einer gegebenen Größe mit
Zufallszahlen zu füllen. Hierbei nehmen die Klasse Hauptfenster.java (Tab1),
Tab2.java und Tab3.java diese Dienste in Anspruch.
Zum einen gibt es hier die Methode erzeugeRandomArray(), die mit der
übergebenen Menge auch dementsprechend viele Zufallszahlen erzeugt. Diese
Zahl ergibt sich je nach der Eingabe des Nutzers auf Tab2 oder Tab3. Das
bedeutet, dass das Feld zwischen 1 und 200.000 Elementen groß ist.
Für die graphische Darstellung der Sortierung war es nötig, eine zweite Methode
einzuführen, die ein Array mit Zufallszahlen füllt, die Anzahl der Elemente ist hier
aber auf den Wert 10 (0-9) beschränkt, da dadurch die Visualisierung vereinfacht
wurde.
Wir haben uns dazu entschieden, zwei Methoden zu erstellen, die ein Feld mit
Zufallszahlen erzeugt, da wir der Meinung sind, dass die Berechnungen bei Tab2
und Tab3 verfälscht werden, wenn man hier nur Zahlen zwischen 0 und 9 nimmt.
Andersrum wäre es ein erheblicher Aufwand gewesen, die Visualisierung der
Sortierung nicht dem festen Wert 10 anzupassen.
Die Methoden gibRandomArray() und getNumbers() geben jeweils das Array
bestehend aus Zufallszahlen an die jeweiligen Klassen zurück.
Seite 28 von 35
3.6.5 Zeitmessung (LW)
Abbildung 26 - Klasse Zeitmessung
Diese Klasse steht den drei Klassen des Paketes „Algorithmen“ zur Verfügung
(BubbleSort.java, InsertionSort.java und SelectionSort.java). Hierbei wird mit
der Methode messeZeit() jeweils durch den Algorithmus vor und nach der
Sortierung die Zeit gemessen. Im nächsten Schritt übergibt der jeweilige
Sortieralgorithmus die Anfangszeit und die Endzeit an die Methode errechneZeit()
und diese ermittelt dann die Dauer und gibt diese zurück.
4. eingesetzte Werkzeuge und Basisliteratur
(LW, LM)
Das gesamte Projekt wurde mit Hilfe von Eclipse SDK Version 3.3.1.1
programmiert und umgesetzt.
Des Weiteren wurden folgende Programme genutzt:
OpenOffice Version 2.3
zur Erstellung der Dokumentation und Präsentation
Adobe Photoshop Version 7.0
zur Erstellung von Grafiken
Visual Paradigm Version 6.1
zur Erstellung von UML-Klassendiagrammen
Zusammenfassend wurden in den meisten Fällen folgende Hilfsmittel genutzt:
Java von Kopf bis Fuß
von Kathy Sierra & Bert Bates
Galileo Computing:: Java ist auch eine Insel
http://www.galileocomputing.de/openbook/javainsel6/
JavaTM 2 Platform Standard Edition 5.0
http://java.sun.com/j2se/1.5.0/docs/api/
Seite 29 von 35
5. Darstellung relevanter Probleme und
deren Lösung (LM, LW)
Im Endeffekt gab es bei der Erstellung des Programms „sorty“ keine größeren
Probleme, die überhaupt nicht gelöst werden konnten.
Ein Problem stellte sich bei der Erstellung eines Timers. Hierbei wollten wir bei
der Sortierung auf dem Tab2 und Tab3 die Möglichkeit haben, dass während der
Sortierung die Zeit hoch läuft, dass heißt, dass man sieht, dass die Sortierung
am Laufen ist und nicht nur am Ende die Gesamtdauer angezeigt wird. Zusätzlich
wollten wir eine kleine Animation, eine tickende, laufende Uhr, während der
Sortierung anzeigen. Jedoch hatten wir hiermit einige Probleme, da die gesamte
Sortierung innerhalb einer inneren Klasse, genauer gesagt eines ActionListeneres
abspielt. Aus uns nicht bekannten Gründen konnten wir so eine selbst
geschriebene Methode nicht innerhalb dieser Methode starten. Außerhalb war
dies kein Problem. Genau dasselbe passierte auch mit der Animation. Nach
etlichen Versuchen und neuen Ideen haben wir im Endeffekt leider keine Lösung
gefunden und da diese Punkte nur als Extras anzusehen sind, haben wir uns
dazu entschlossen, den Timer und die Animation nicht mit einzubauen.
Im Folgenden sind nun noch vier Probleme aufgelistet, an denen wir viel Zeit
investiert und am Ende auch eine Lösung gefunden haben.
1. Problem – Highlighter (LM)
Um in dem JtextArea pseudoCode die einzelnen Zeilen zu markieren, wurde
zuerst die Methode select() genutzt, was auch funktioniert hat. Jedoch war hier
ein sehr großer Nachteil, das beim anklicken des Fenster oder der Buttons die
Zeile wieder deselektiert wurde. Da wir mittels des Pause-Buttons eine
Möglichkeit bieten wollten, die einzelnen Komponenten genauer zu betrachten,
war dies ein Problem, da man evtl. nicht mehr nachvollziehen konnte, in welcher
Zeile der Algorithmus sich gerade befindet.
Um dieses Problem zu lösen, haben wir uns für den Einsatz eines Highlighters
entschlossen.
Ein Highlighter ermöglicht es einem, bestimmte Bereiche in einer bestimmten
Farbe zu markieren, wie die Methode select(), nur mit dem Vorteil, dass die
Zeilen auf jeden Fall markiert bleiben.
Der Highlighter wurde folgendermaßen realisiert:
private Highlighter highlight = pseudoCode.getHighlighter();
public void zeileMarkieren(int zeilenAnfang, int zeilenEnde){
highlight.removeAllHighlights();
try {
start = pseudoCode.getLineStartOffset(zeilenAnfang);
ende = pseudoCode.getLineEndOffset(zeilenEnde);
highlight.addHighlight(start, ende,
DefaultHighlighter.DefaultPainter);
} catch (Exception e1) {}
pseudoCode.repaint();
}
Bei dem Aufruf der Methode zeileMarkieren() wird der Zeilenanfang und der
Zeilenende der Zeile übergeben, die markiert werden soll. Der Aufruf der
Seite 30 von 35
Methode addHighlight(start, ende, DefaultHighlighter.DefaultPainter) markiert die
Zeile in der Farbe, die Standardmäßig eingestellt ist.
2. Problem – RandomArray (LM)
Für die visuelle Darstellung des Sortiervorgangs haben wir eine Zahlenmenge der
Größe 15 festgelegt mit Zahlen von 0 bis 9. Dementsprechend wurden Konstante
Werte für die Größe und Farbe der 10 Möglichen Zahlen festgelegt. Da wir aber
bei der zeitlichen Berechnung zusätzlich noch größere Zahlen verwenden wollten,
haben wir uns dazu entschlossen, zwei verschiedene Methoden für die
Zufallszahlenerzeugung zu erstellen.
Die Methode erzeugeRandomArray() erzeugt ein Feld mit Zufallszahlen zwischen
1 und der vom Anwender eingegebenen Menge. Diese Methode wird für die
zeitliche Berechnung und den zeitlichen Vergleich verwendet.
Die Methode setzeNummern() erzeugt ein Feld mit Zufallszahlen zwischen 0 und
9, die für die visuelle Darstellung genutzt wird.
3. Problem – getInstance() (LW)
Das Programm “sorty” besteht insgesamt aus 15 Klassen. Hierbei kommt es oft
vor, dass einige Klassen Zugriff auf die wichtigste Klasse, die Hauptfenster.java,
benötigen.
Für den Fall, dass es notwendig war, wurde immer beim Methoden- oder
Konstruktor-Aufruf das Objekt der Klasse Hauptfenster mit übergeben.
Zum Beispiel startet man das Hauptfenster das erste Mal, indem man bei dem
Auswahlfenster auf einen Button klickt. Wenn man nun im Hauptfenster die
Möglichkeit „Zurueck zur Auswahl“ nutzt, gelangt man wieder zu dieser Auswahl.
Bisher haben wir an dieser Stelle immer ein neues Objekt der Klasse
Hauptfenster.java erzeugt.
Da dies aber irgendwann zu Problemen und zur Unübersichtlichkeit führt, haben
wir lange nach einer Lösung gesucht, wie man dieses Problem in den Griff
bekommt.
Letztendlich haben wir folgenden Codeausschnitt in die Klasse Hauptfenster.java
eingefügt:
private static Hauptfenster HAUPTFENSTER;
public static Hauptfenster getInstance (String algorithmus)
{
if (HAUPTFENSTER == null)
{
HAUPTFENSTER = new Hauptfenster (algorithmus);
}
return HAUPTFENSTER;
}
Da die Methode getInstance() static ist, hat man aus dem gesamten Programm
Zugriff auf diese Methode. Beim Aufruf wird zunächst überprüft, ob schon ein
Objekt der Klasse Hauptfenster erstellt wurde, wenn dies nicht der Fall ist, wird
ein neues Objekt erzeugt. Das passiert bei dem Aufruf von der Klasse
AuswahlAlgorithmen.java. Ab diesem Punkt existiert ein Objekt und die Variable
ist nicht mehr null, deshalb wird dann das Objekt von Hauptfenster
zurückgegeben.
Mit dieser Methode ist es sehr einfach und elegant, auf das Hauptfenster und
deren Methoden zuzugreifen, ohne das Objekt mit übergeben oder erstellen zu
müssen.
Seite 31 von 35
4. Problem – Array clonen (LW)
Dieses Problem trat bei dem dritten Tab (Vergleich der Algorithmen) auf. Hierbei
wird ein Array erzeugt und dieses Array soll von allen Sortierverfahren sortiert
werden.
Hierzu erzeugen wir zunächst mit Hilfe der Klasse RandomArray.java das Feld
bestehend aus Zufallszahlen. Im Folgenden ist eine Variante zu sehen, die wir
ausprobiert haben.
random.erzeugeRandomArray (menge);
intArrayBubble = random.gibRandomArray ();
intArrayInsertion = intArrayBubble;
intArraySelection = intArrayBubble;
Danach haben wird das Array jeweils für die Algorithmen abgespeichert, sodass
auch jeder das gleiche Array sortiert und dann beginnt die Sortierung. Jedoch
hatten wir immer wieder das Problem, dass bei dem 2. und 3. Array immer schon
sortierte Arrays ankamen, dass heißt, die Dauer auch auf 0 Millisekunden lag.
Wir konnten uns nicht erklären, warum die Sortierung des ersten Arrays
funktionierte und dann die anderen beiden Arrays, die ja separat abgespeichert
waren, schon die sortierte Menge ankam.
Nach langem Suchen und Probieren konnte uns dann ein Kommilitone helfen.
Dadurch, dass wir das Array, wie unter Anderem im oberen Beispiel, einfach
gleichgesetzt haben, sieht Java das immer noch als ein Array an und so werden
die Änderungen in dem einen Array in den anderen Arrays mitgespeichert. Im
Endeffekt, sieht also die Lösung wie folgt aus:
random.erzeugeRandomArray (menge);
intArrayBubble = random.gibRandomArray ();
intArrayInsertion = intArrayBubble.clone ();
intArraySelection = intArrayBubble.clone ();
Hier wird nun das eine Array zweimal geklont, so wirken sich die Änderungen an
dem einen nicht mehr auf die anderen beiden aus.
6. Darstellung des Aufwandes (LW, LM)
Für den reinen Programmieraufwand lässt sich zusammenfassend sagen, dass
wir ungefähr 65 Stunden pro Person in das Projekt gesteckt haben. Hierbei
wurde von beiden Personen ungefähr die gleiche Zeit hineingesteckt.
Von den 65 Stunden wurden ca. 40 Stunden für die Programmierung der
Basisfunktionen, dass heißt für die Ziele im Projektantrag, investiert.
Die restlichen 25 Stunden wurden dann für die Optimierung und
Benutzerfreundlichkeit genutzt.
Das Sammeln von Informationen und das Lösen von Problemen ist in den 65
Stunden enthalten.
Seite 32 von 35
7. Fazit (LM, LW)
Gesamt betrachtet lässt sich sagen, dass wir mit unserem Projekt, dem
Programm sorty, sehr zufrieden sind.
Die im Projektantrag gestellten Ziele wurden alle erreicht. Die wichtigsten
werden im Folgenden nochmals kurz dargestellt:
Umsetzung der Sortieralgorithmen Bubblesort, Insertionsort
Selectionsort
Visualisierung
o Graphische Darstellung anhand von Säulen
o Ablauf des Pseudocodes parallel zur Sortierung
o Darstellung der Umgebung und Tabs
o Berechnung der Dauer der Sortieralgorithmen (Tab2)
und
Darüber hinaus haben wir die optionalen Komponenten Start-/Stop-Funktion bei
der visuellen Sortierung und eine zusätzliche schriftliche Erklärung parallel zum
Sortiervorgang umgesetzt. Zur Umsetzung dieser Punkte haben wir uns
entschlossen, um unser Projekt zu optimieren und benutzerfreundlicher zu
gestalten.
Die optionale Komponente Animation und die Umsetzung mittels Java3d haben
wir aus Zeitgründen nicht umsetzen können.
Während der Entwicklung unseres Projektes kamen wir auf die Idee, eine
zusätzliche Funktion einzuführen. Wir waren der Meinung, es wäre interessant
einen Vergleich zwischen den einzelnen Sortierverfahren zur Verfügung zu
stellen. Somit haben wir einen zusätzlichen Tab eingeführt, der für diesen
zeitlichen Vergleich zuständig ist.
Außerdem haben wir zusätzlich die Möglichkeit eingebaut, dass der Nutzer vor
der Sortierung die Geschwindigkeit der visuellen Sortierung einstellen kann.
Um die Benutzerfreundlichkeit und auch die Funktionalität unseres Programms zu
Testen, haben wir an verschiedenen Meilensteinen unseres Projektes Studierende
und auch Nicht-Studierende ohne Hilfe unser Programm testen lassen.
Hierbei bekamen wir gerade am abschließenden Stand unseres Programms sehr
positive Resonanz. Die Testpersonen gaben an, dass das Programm generell sehr
einfach zu verstehen ist, eine klare Strukturierung vorliegt und viele Hilfen
geboten sind.
Verbesserungsvorschläge
Neue Randomzahlen
Wird bei dem Sortiervorgang der Button neue Randomzahlen gedrückt werden
während der aktuellen Sortierung neue Zahlen erzeugt und auch in das Feld
gemalt. Das Programm sortiert ungestört weiter.
Sortiere Button
Wird während dem Sortiervorgang der Button Sortiere geklickt, wird ein neuer
Thread gestartet. Der alte Thread ist dann nicht mehr ansprechbar, d.h. er kann
nicht pausiert oder gestoppt werden.
Seite 33 von 35
Stop-Funktion für Tab2 und Tab3
Auf dem Tab 2 und Tab 3 gibt es keine Möglichkeit, den Sortiervorgang
abzubrechen. Dies wäre von Vorteil, wenn man eine besonders große Zahl
eingegeben hat und nicht bis zum Ende warten möchte.
8. Quellen
[1] Wikipedia – Die freie Enzyklopädie
http://www.wikipedia.de
[2] Herr Prof. Dr. Ehrenberger
Skript: Algorithmen und Datenstrukturen
[3] Mycsresource.net – Sorting Algorithms
http://www.mycsresource.net/articles/programming/sorting_algos/bubble
sort
9. Anhang
Bild zum Punkt 3.3.3 Hauptfenster
Seite 34 von 35
Seite 35 von 35

Visualisierung der Sortieralgorithmen Bubblesort, Insertionsort und

Transcrição

Documentos relacionados

ra$.Nffiw^t

Lisa Feller

SPS-Programmierer / in

223 Schulabgänger feierlich entlassen - i

TOP 10 Fitness Mehrkampf - Anna - Seghers

zh_1-06 korr2 2.indd

Colloquiumszyklus „Paris und die Folgen“

der Flyer mit weiteren Details - Marien

D Fallen Presseinfo

Leergutmanagement auf höchstem Niveau.