Python 3-Wege-Partitionierung (Quicksort)

Question

Ich versuche, einen Python-Code für die 3-Wege-Partition zu schreiben, aber ich bekomme einen Indexierungsfehler. Ich habe versucht, es zu beheben, scheint aber nicht erfolgreich zu sein. In meinem Code wähle ich den ersten Eintrag als Pivot und scanne dann von links und von rechts und tausche die Werte wenn nötig. Wenn irgendein Eintrag gleich pivot ist, verschiebe ich ihn entweder an den Anfang oder an das Ende (wo ich einen Fehler erhalte) von a.

Dies ist mein Code

def partition(a, start, end): 
    left=start+1 
    right=end 
    p=start+1 
    q=end 
    pivot=a[start] 
    while True: 
     while a[left]<pivot: 
      left+=1 
     while a[right]>pivot: 
      right-=1 
      if right==start+1: 
       break 
     if left>=right: 
      break 
     swap(a[left], a[right]) 
     if a[left]==pivot: 
      swap(a[p],a[left]) 
      p+=1 
     if a[right]==pivot: 
      swap(a[right], a[q]) 
      q-=1 
    swap(a[right], a[start]) 
    k=end 
    while k>=q+1: 
     swap(a[left+1], a[k]) 
     k-=1 
     left+=1 
    k=1 
    while k<p: 
     swap(a[k], a[right+1]) 
     k+=1 
     right-=1 

und definiere ich Swap als:

def swap(a, b): 
    temp=a 
    a=b 
    b=temp 

wenn ich versuche, diese Funktion ich einen Fehler in Zeile 21, diesen Index außerhalb des zulässigen Bereichs erhalten laufen. Irgendwelche Vorschläge, was hier falsch ist?

Answer 1

Wie in den Kommentaren zu der Frage bemerkt, die swap() Funktion in Ihrem Code tut nichts. In Python sind Namen nur Labels, die an Objekte angehängt sind. Wenn Sie einem Namen zuweisen, fügen Sie einfach ein Label an ein Objekt an. Wenn Sie ein Objekt an eine Funktion übergeben, wird das Objekt übergeben, nicht die ihm zugewiesenen Namen. Zuweisungen innerhalb einer Funktion erstellen nur lokale Namen für ein Objekt, haben jedoch keinen sichtbaren Effekt außerhalb der Funktion.

Sie können die in eine Funktion übergebenen Objekte jedoch ändern. Die folgende Implementierung von swap() funktionieren würde:

def swap(a, i, j): 
    a[i], a[j] = a[j], a[i] 

Es ändert die Liste als a eingeleitet.