Quicksort Implementierung in Python

Question

Ich versuche, eine schnelle Art anstelle Funktion zu schreiben hier ist mein Code

def quick_sort(ar): 
    if len(ar) < 2: 
     return ar 
    pivot = ar[-1] 
    i = 0 

    for j in range(len(ar)): 
     if ar[j] < pivot: 
      ar[i], ar[j] = ar[j] , ar[i] 
      i += 1 
    ar[i], ar[-1] = ar[-1], ar[i] 

    quick_sort(ar[0:i]) 
    quick_sort(ar[i+1:]) 

    return ar 


lst = [1, 3, 9, 8, 2, 7, 5] 
print quick_sort(lst) 

aber ich bekomme eine leere Liste im Gegenzug .. was ich hier fehlt?

Answer 1

Ihre rekursiven Aufrufe werden an Slices Ihrer Liste vorgenommen. Beim Slicen wird eine Kopie erstellt, sodass die Rekursion die ursprüngliche Liste überhaupt nicht ändert. Sie müssen entweder die Rückgabewerte der rekursiven Aufrufe verwenden oder alles direkt ausführen. Jede dieser erfordert einige Änderungen an Ihrem Code, nur an verschiedenen Orten

Hier ist eine Version des Codes, der eine neue Liste erstellt:

def quick_sort(ar): 
    if len(ar) < 2: 
     return ar 
    pivot = ar[-1] 
    i = 0 

    for j in range(len(ar)): 
     if ar[j] < pivot: 
      ar[i], ar[j] = ar[j] , ar[i] 
      i += 1 
    ar[i], ar[-1] = ar[-1], ar[i] 

    result = quick_sort(ar[0:i]) # build a new result list from the recursive calls 
    result.append(pivot) 
    result.extend(quick_sort(ar[i+1:])) 

    return result 

Und hier ist eine, die an Ort und Stelle sortiert:

def quick_sort(ar, low=0, high=None): # get sorting bounds as arguments 
    if high is None: 
     high = len(ar) 
    if high - low < 2: 
     return 
    pivot = ar[high-1] 
    i = low 

    for j in range(low, high): # iterate on a limited range 
     if ar[j] < pivot: 
      ar[i], ar[j] = ar[j] , ar[i] 
      i += 1 
    ar[i], ar[high-1] = ar[high-1], ar[i] 

    quick_sort(ar, low, i) 
    quick_sort(ar, i+1, high) 

    # no need to return anything, since we sorted ar in place 

In Anbetracht wie Sie die Partitionierung machen, macht die In-Place-Version wahrscheinlich mehr Sinn. Die andere Version wäre interessanter, wenn sie mit einem Partitionierungsschema gepaart wäre, das eine stabile Sortierung ermöglichte (es gibt keine einfache Möglichkeit, einen stabilen Quicksort an Ort und Stelle zu machen).