Quicksort – Anfang der Implementierung

Zu Beginn der Stunde wurde zur Wiederholung mit Filmdöschen und einer Waage vorgeführt, wie Quicksort in etwa abläuft. Grob zusammengefasst: Man pickt sich ein Element raus und vergleicht es mit allen anderen Elementen. Dabei werden zwei Listen erstellt, in eine kommen die Elemente hinein, die kleiner als das Pivotelement(das Herausgepickte) sind. In die andere kommen die Elemente rein, die größer als das Pivotelement sind. Dieser Vorgang wird rekursiv mit den neu entstandenen Listen wiederholt, bis die Liste sortiert ist. Herr Karp erwähnte zudem auch noch, dass das „maximale Glück“ dann erreicht wird, wenn das Pivotelement immer in etwa eine mittlere Zahl ist und die beiden Listen, die entstehen in etwa gleich groß sind. In diesem Fall ist Quicksort am schnellsten.

Daraufhin haben wir besprochen wie in etwa die Implementierung von Quicksort aussehen könnte, was dann unsere Aufgabe war. Als Hausaufgabe sollten wir dann Quicksort zu Ende programmieren und die Laufzeit testen.

Folgende Vorlage dient als Hilfe zur Implementierung von Quicksort und die Zeilen sind weder eingerückt, noch in der richtigen Reihenfolge:

return lSortiert
g=[]
else:
return 1
k=[]
lSortiert=kSortiert+[pivot]+gSortiert
gSortiert=quicksort(g)
if e < pivot:
k+=[e]
else:
for e in l[1:]:
pivot=l[0]
def quicksort(l):
g+=[e]
kSortiert=quicksort(k)
if len(l) > 1:

from random import *
liste = [randint(0,10000) for i in range(100)]
print(liste)
print(quicksort(liste))

Ein Kommentar zu „Quicksort – Anfang der Implementierung

Schreibe einen Kommentar