Quicksort
Der Quicksort-Algorithmus ist ein Algorithmus, mit welchem sich auch große Listen schnell sortieren lassen. Er ist rekursiv und nutzt das Divide-And-Conquer-Prinzip.
Videoerklärung
Implementierung
Python
Ich habe den Algorithmus in Python mit den sogenannten List Comprehensions implementiert. Im Beispiel sortiert er die ungeordnete Ziffernfolge 1-10.
1 2 3 4 5 6 7 8 9 10 11 12 13 | #!/usr/bin/env python
def quicksort(liste):
if len(liste) <= 1:
return liste
pivot = liste.pop(0)
groessergleich = quicksort([i for i in liste if i >= pivot])
kleiner = quicksort([i for i in liste if i < pivot])
return kleiner + [pivot] + groessergleich
if __name__ == "__main__":
liste = [3,6,1,8,5,10,9,2,7,4]
print quicksort(liste)
|
Java
Dustin und ich hatten im Informatik-Unterricht den Quicksort-Algorithmus in Java implementiert. Zusätzlich haben wir eine GUI, welche die notwendigen Vergleiche und Rechenoperationen anzeigt hinzugefügt. Den Code findet ihr hier.
Post comment
Zum Kommentieren musst du angemeldet sein.
2 comments
Duferkamp am March 6, 2010 um 1:31 a.m.
BlitzChecker am March 6, 2010 um 10:50 a.m.