|
|
Übung 1 Übung
3
Ü B U N G 2
Aufgabe 1
Bucket Sort: Bei Bucket-Sort handelt es sich um ein
nicht vergleichsbasiertes Sortierverfahren. Hier werden z.B. Zahlen
a1...an aus dem Bereich {0...N-1} dadurch sortiert, dass sie in
durchnummerierte "Eimer" (Buckets) 0...N-1 geworfen werden. Die
Inhalte dieser Eimer werden dann nacheinander ausgegeben, man erhält
eine sortierte Folge. N gibt dabei den Wertebereich vor,
d.h. es können Zahlenfolgen mit Werten von 0 bis N-1 sortiert
werden.
Beispiel: Zahlenfolge: 2 1 3 1 2 ,
N=4 Wertebereich: N=4 => Zahlen mit den Werten 0 - 3 können
sortiert werden. In der Zahlenfolge oben kommen Zahlen von 1 bis 3
vor, sie liegen also alle im Wertebereich.
Nun werden
nacheinander die Zahlen der Folge in die entsprechenden Eimer
"geworfen": Die beiden Einsen landen in Eimer 1, die Zweien in
Eimer 2 und die Drei in Eimer 3. Jetzt brauchen die Eimer nur noch
in der richtigen Reihenfolge nacheinander ausgeleert werden.
Schreiben Sie eine Klasse BucketSort, die die
statische Methode sort und eine statische Variable N
(Wertebereich) enthält. Die Methode sort soll ein int-array
als Eingabeparameter erwarten und ebenfalls ein int-array
zurückgeben. Testen Sie Ihre sort-Methode in der main-Methode
mit den folgenden Werten: 4, 2, 4, 28, 19, 255, 87, 0, 8,
103 Wie groß muss N in diesem Fall mindestens gewählt werden?
Visualisierung verschiedener Sortierverfahren
Download der Lösung (BucketSort.java)
(Java-Applet)
Zusatzaufgabe
Erweitern Sie die Klasse BucketSort um eine Methode
sortChar, die diesmal ein Character-Array als
Eingabeparameter erwartet bzw. ein Character-Array zurückgibt. Diese
Methode soll nun nicht mehr nur Zahlen, sondern auch Buchstaben nach
dem Bucket-Sort-Verfahren sortieren.
Testen Sie diese Methode
ebenfalls in der main-Methode. Was fällt Ihnen auf, wenn Sie eine
Zeichenfolge sortieren, die sowohl Groß- als auch Kleinbuchstaben
enthält?
Aufgabe 2
Der BubbleSort-Algorithmus kann dazu benutzt werden, eine Reihe
von Zahlen in einem Array der Länge n zu sortieren. Bubblesort ist
einer der einfachsten (aber auch langsamsten) Sortieralgorithmen und
die Theorie ist verhältnismäßig einfach. Der Algorithmus führt
folgende Schritte aus:
- Man durchläuft das gesamte Feld von vorne bis hinten n-1 mal.
- Man vergleicht die benachbarten Zahlen.
- Falls das linke Element größer ist als das rechte Element,
sollen die beiden Zahlen vertauscht werden.
Implementieren Sie BubbleSort in Java!
Beispiel:
Unsortiertes Array: [8,5,2,3]
1. Durchlauf:
Vergleich von 8 und 5 --> Vertauschen: [5,8,2,3]
Vergleich von 8 und 2 --> Vertauschen: [5,2,8,3]
Vergleich von 8 und 3 --> Vertauschen: [5,2,3,8]
2. Durchlauf:
Vergleich von 5 und 2 --> Vertauschen: [2,5,3,8]
Vergleich von 5 und 3 --> Vertauschen: [2,3,5,8]
Vergleich von 5 und 8 --> kein Vertauschen [2,3,5,8]
3. Durchlauf:
Vergleich von 2 und 3 --> kein Vertauschen: [2,3,5,8]
Vergleich von 3 und 5 --> kein Vertauschen: [2,3,5,8]
Vergleich von 5 und 8 --> kein Vertauschen: [2,3,5,8]
Sortiertes Array: [2,3,5,8]
Download der Lösung (BubbleSort1.java)
Zusatzaufgabe
Überlegen Sie sich, wie der BubbleSort-Algorithmus aus Aufgabe 1 verbessert werden könnte. Ist es nötig, in jedem Durchlauf das
gesamte Feld zu durchlaufen ?
Download der Lösung (BubbleSort2.java)
| |