Im Laufe unserer Prüfungsvorbereitung haben wir den Quicksort-Algorithmus in Java implementiert.
Kurze Erklärung zum Algorithmus:
Wir legen ein Array an mit einer Folge von unsortierten Zahlen. In diesem Array wählt man nun ein Pivot-Element. Für die Wahl des Elements gibt es mehrere Ansätze, jedoch bevorzugen wir das Element in der Mitte der Liste zu wählen. Ziel des Algorithmus ist nun durch Vertauschen, dass links vom Pivot-Element alle Zahlen kleiner sind, und rechts davon alle größer. Nun wird die Liste in zwei Teile geteilt und der Algorithmus fängt von vorne wieder an und arbeitet die entstehenden Teillisten ab.
Beispiel:
Wir sotieren:
Das Pivot-Element ist die 10. Nun läuft der Index durch. i zeigt auf das Element 34, j auf das Element 12. Ist das Element an der Stelle i (34) < Pivot, NEIN! Also laufe mit j weiter. Ist das Element an der Stelle j (12) > Pivot, JA! Erniedrige j um 1. Ist das Element an der Stelle j (7) > Pivot, NEIN! Somit tausche die 34 und die 7 und erhöhe danach i um 1 und erniedrige j um 1. Die Abbruchbedingung ist, falls sich i und j überschneiden. Dann wird der Algorithmus für die Teillisten analog abgearbeitet.
Weiterführung des Beispiels:
| 34 |
9 |
10 |
7 |
12 |
| 7 |
9 |
10 |
34 |
12 |
| 7 |
9 |
10 |
34 |
12 |
| 7 |
9 |
10 |
12 |
34 |
| 7 |
9 |
10 |
12 |
34 |
In der 2. Zeile ist der Normalfall. Das heißt das Pivot-Element wird nicht in eine der Teillisten mitgenommen. Die trifft nur zu wenn i und j beim vorletzten Schritt auf das Pivot-Element zeigen. Im letzten Schritt wird i erhöht und j erniedrigt. Somit ergeben sich die Teillisten (7, 9) und (34, 12).
Zum selber ausprobieren könnt ihr den Quelltext hier runterladen: Quicksort.java
Letzte Kommentare