Das deutsche Python-Forum

Hallo Zusammen,
in der Schle beschäftigen wir uns jetzt mit dem Quicksort Algorithmus. Jetzt bin ich dabei über diesen Code gestolpert. Und meine Frage dazu ist, ob mir den Vielleicht jemand erklären kann, was da in den Zeilen Passiert. Wie der Quicksort Algorithmus in der Theorie funktioniert ist mir klar, nur mit diesem Code komm ich nicht weiter..

Code: Alles auswählen

def quicksort(L, anfang, ende):
    if L != []:
        pivot = L[anfang]
        links = anfang
        rechts = ende
        while links <= rechts:
            while L[links] < pivot:
                links = links+1
            while L[rechts] > pivot:
                rechts = rechts-1
            if links <= rechts:
                if links < rechts:
                    h = L[links]
                    L[links] = L[rechts]
                    L[rechts] = h
                links = links+1
                rechts = rechts-1
            print(L)
            print(anfang, ende, links, rechts)
        print()
        if anfang < rechts:
            L = quicksort(L, anfang, rechts)
        if links < ende:
            L = quicksort(L, links, ende)
    return L

# Test
L = [25, 17, 32, 56, 25, 19, 8, 66, 29, 6, 20, 29]
print(L)
L = quicksort(L, 0, len(L)-1)
print(L)

Danke schonmal im Voraus

@eXodus: Du mußt schon konkreter Fragen, was Du nicht verstehst. Der Code enthält syntaktisch nichts, was über Anfängerniveau gehen würde. Der Code ist tückisch, weil er sowohl die Liste zurückgibt, als sie auch inplace verändert. Die passende List-Methode liefert dagegen None zurück.

Anhand der Theorie zu Quicksort die du ja verstanden hast und deinen Debugging-Ausgaben solltest du eigentlich recht gut erkennen können was passiert. Wichtig ist die Beachtung des rekursiven Aufrufs für die jeweils zu sortierenden Teile der Liste.

An welcher Stelle steigst du denn vom Verständnis her aus?

Es gibt übrigens im Code Stellen die man schöner schreiben kann.

Code: Alles auswählen

links = links + 1

# schöner mit einem augmented assignment
links += 1

#
h = L[links]
L[links] = L[rechts]
L[rechts] = h

# besser ohne Hilfsvariable mit Tuple-Packing/Unpacking
L[links], L[rechts] = L[rechts, L[links]

Etwas unglücklich ist es, dass die als Parameter übergebene Liste modifiziert und zusätzlich noch zurückgegeben wird. Eins von beidem reicht.

Code: Alles auswählen

while L[links] < pivot:
                links = links+1

Nur Ist der Pivotelement ja auch das linke Element aus der Liste, also sollte bei diesem Teil des Codes doch überhaupt nichts passieren oder?

Dann wenn hier:

Code: Alles auswählen

while L[links] < pivot:
                links = links+1
while L[rechts] > pivot:
                rechts = rechts-1

die Indexe der Liste verschoben werden, z.B. der letzte Index eins nach links, weil das Element größer als das Pivotelement ist, was passiert dann mit dem Index auf dessen Platz das es geschoben wird?
Also in der Liste aus dem Beispiel ist das letzte Element die 29, diese ist ja größer als 25, also sollte es einen Platz weiter nach links rücken laut Code, doch was passiert dann mit der 20, die links von der 29 steh?

@eXodus: Spiel das doch einfach mal mit Papier und Bleistift durch, dann siehst Du was in jedem Schritt genau passiert.

Das deutsche Python-Forum

Quicksort Algorithmus

Quicksort Algorithmus

Re: Quicksort Algorithmus

Re: Quicksort Algorithmus

Re: Quicksort Algorithmus

Re: Quicksort Algorithmus