Quick-Sort

Hefteintrag

Algorithmus
Ein ausgewähltes Element ist an die ausgewählte Arrayposition zu bringen. Dazu sind n-1 Vergleiche notwendig.

11
  
03
  
21
  
42
  
08
  
07
 
11 sei das ausgewählte Element ai. Bei der Suche von links ist die 21 das erste Element > 11. Diese wird in die linke Hand genommen. Nun beginnt von rechts die Suche bis zu dem Element, das kleiner (oder gleich) als 11 ist. Dieses - die 07 - wird in die rechte Hand genommen. Nun werden 21 und 07 miteinander getauscht.
11
  
03
  
07
  
42
  
08
  
21
 
Nun wird wieder von links aus gesucht und zwar bei der Position, die im vorigen (linken) Durchlauf noch nicht betrachtet wurde. Das Element 42 wird in die linke Hand genommen und es wird nun von rechts gesucht, beginnend bei der Position, die noch nicht besucht wurde. Also wird 08 in die rechte Hand genommen und beide Elemente werden miteinander getauscht.
11
  
03
  
07
  
08
  
42
  
21
 
Wenn sich in der Fortsetzung dieses Prozesses linke mit rechter Suche kreuzt , wird das Element in der linken Hand zurückgelegt, das der rechten mit dem zu Beginn gewählten Element hier die 11 - getauscht.
08
  
03
  
07
  
11
  
42
  
21
 
Element 11 ist nun auf dem endgültigen Platz. Nacheinander wird nun das Verfahren für den Bereich links von der 11 und für den Bereich rechts von der 11 separat angewendet. (-> Rekursion)
07
  
03
  
08
  
11
  
21
  
42
 
Element 11 ist nun auf dem endgültigen Platz. Nacheinander wird nun das Verfahren für den Bereich links von der 11 und für den Bereich rechts von der 11 separat angewendet. (-> Rekursion)
03
  
07
  
08
  
11
  
21
  
42
 
Element 11 ist nun auf dem endgültigen Platz. Nacheinander wird nun das Verfahren für den Bereich links von der 11 und für den Bereich rechts von der 11 separat angewendet. (-> Rekursion)

- Suche links links von ai ein Element, das größer als ai ist.

- Suche rechts rechts von ai ein Element, das kleiner als ai ist.

- Wenn beide Elemente gefunden: vertauschen

- Wenn nur ein Elemenent gefunden: mit ai vertauschen


1. Erläuterung und Animation (empfehlenswert) , hier als Archiv
2. Erläuterung mittels Applet , interaktiv
3. Erläuterung für Beispiel mit Pivotelement an letzter Stelle
4. Demoprogramm

Hefteintrag

Aufgabe a) Vergleichen Sie Sortieralgorithmen. Suchen Sie im Demo den langsamsten Sortieralgorithmus!