Quicksort

Ein weiterer, sehr effizienter Algorithmus zum Sortieren großer Datenmengen ist Quicksort. Auch Quicksort findet sich in zahlreichen aktuellen Bibliotheksimplementationen moderner Programmiersprachen wieder. Quicksort wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von andren Forschern verbessert.

• (Man vermischt das Array aus hat Performanzgründen)
• Man wählt das erste Element¹⁾ als Pivotelement und ordnet anschließend alle Elemente so an, dass das Pivotelement das Array in zwei Teile teilt: Die Elemente des ersten Teilarrays sind alle kleiner als das Pivotelement, die Elemente des zweiten Teilarrays sind alle größer als das Pivotelement.
• Anschließed verfährt man mit den Teilarrays rekursiv analog.

Im ersten Schritt teilt man das Array bezüglich eines Pivotelements in zwei Teile: Alle Elemente links des Pivotelements sollen kleiner sein als dieses, alle rechts davon größer.

Nun kann man (letztlich rekursiv) das Verfahren auf die beiden Teilarrays (im Bild orange, bzw. blau) erneut anwenden.

Führe das Verfahren für beide Teilarrays von Hand erneut aus.