Quicksort mit Python

89

Ich bin völlig neu in Python und ich versuche, Quicksort darin zu implementieren. Könnte mir bitte jemand helfen, meinen Code zu vervollständigen?

Ich weiß nicht, wie ich die drei Arrays verketten und drucken soll.

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
            sort(less)
            sort(pivot)
            sort(greater)
user2687481
quelle
Zum Kombinieren von Listen können Sie den Operator plus verwenden my_list = list1 + list2 + .... Oder packen Sie Listen in eine neue Liste ausmy_list = [*list1, *list2]
Mark Mishyn

Antworten:

248
def sort(array=[12,4,5,6,7,3,1,15]):
    """Sort the array by using quicksort."""

    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)
        # Don't forget to return something!
        return sort(less)+equal+sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array
Brionius
quelle
8
Sie können auch die 2. ifs in der for-Schleife mit elifelse
austauschen
13
Dies klingt wie Zusammenführen Sortieren nicht schnell sortieren
Emad Mokhtar
46
Es ist eigentlich die beste und am besten lesen Python Code , den ich für quicksort gefunden überall . Keine Indizes, keine Hilfsfunktionen zeigen deutlich den Kern des Algorithmus (Teilen und Erobern). (Der Standardwert für das Array ist eher unnötig)
cmantas
19
@jsmedmar es wird mehr Speicher als eine In-Place-Version verbrauchen, siehe Suquants Antwort für eine In-Place-Schnellsortierung.
John
14
Sehr gut lesbar, aber besiegt dies nicht den Zweck der schnellen Sortierung, da dadurch keine Sortierung an Ort und Stelle erreicht wird? @RasmiRanjanNayak sort hier ist die benutzerdefinierte Funktion (es ist ein rekursiver Aufruf), keine eingebaute Funktion.
Maksood
159

Schnelle Sortierung ohne zusätzlichen Speicher (vorhanden)

Verwendung:

array = [97, 200, 100, 101, 211, 107]
quicksort(array)
# array -> [97, 100, 101, 107, 200, 211]
def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot



def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)
suquant
quelle
23
Dies sollte die ausgewählte Antwort sein, da Quicksort häufig der Algorithmus der Wahl ist (z. B. über Zusammenführungssortierung), da er an Ort und Stelle sortiert wird (und dennoch die Laufzeit O (nlogn) ergibt).
BoltzmannBrain
3
if end is None:wird oft überprüft, und nur einmal wird es sein True. Sie sollten dies in eine Wrapper-Funktion einfügen, damit es nur einmal aufgerufen wird.
Gillespie
Ackchyually, bruhs, @mksteve ist richtig und diese Zeile ist falsch. Darüber hinaus array[pivot], array[begin] = array[begin], array[pivot]sollte ersetzen beginmit end.
Ryan J McCall
2
Obwohl In-Place gut ist, ist dies langsam und es tritt ein Fehler auf, da die maximale Rekursionstiefe erreicht wird, wenn viele Elemente vorhanden sind. siehe repl.it/@almenon/quicksorts?language=python3
Almenon
@mksteve und Ryan, ich habe diese Änderungen getestet und es bricht die Sortierungen
aljgom
68

Es gibt eine andere prägnante und schöne Version

def qsort(arr): 
    if len(arr) <= 1:
        return arr
    else:
        return qsort([x for x in arr[1:] if x < arr[0]]) + \
               [arr[0]] + \
               qsort([x for x in arr[1:] if x >= arr[0]])

# this comment is just to improve readability due to horizontal scroll!!!

Lassen Sie mich die obigen Codes für Details erklären

  1. Wählen Sie das erste Element des Arrays arr[0]als Drehpunkt

    [arr[0]]

  2. qsort die Elemente des Arrays, mit denen weniger als geschwenkt wird List Comprehension

    qsort([x for x in arr[1:] if x < arr[0]])

  3. qsort die Elemente des Arrays, die größer sind als Pivot mit List Comprehension

    qsort([x for x in arr[1:] if x >= arr[0]])

zangw
quelle
15
@zangw mögliche Gründe für eine Abwertung: 1) Quadratische Laufzeit auf bereits sortierten oder umgekehrten Arrays 2) Die Lösung ist nicht vorhanden. Daher eine schreckliche Implementierung, sorry.
Alisianoi
15
Versuchen Sie wirklich, die Anzahl der Zeilen zu minimieren? Code wird von Maschinen interpretiert, aber vom Menschen verstanden.
jsmedmar
4
@AlfredoGallegos, der springende Punkt bei Quicksort ist, dass es an Ort und Stelle passiert. Sie können auch Merge-Sort implementieren, wenn Sie dies tun.
Padraic Cunningham
13
Sind diese Kommentare echt? Wenn Sie Leistung wünschen, verwenden Sie sorteddiese eindeutig zu Bildungszwecken. Und es ist lesbar, besser lesbar als die akzeptierte Antwort.
Nobilis
3
FWIW, ich dachte, dies sei die am besten lesbare Implementierung von allen. Es zeigt die rekursive Struktur des Algorithmus besser als jede andere Antwort. Natürlich wird die Leistung nicht zu groß sein.
SolveIt
35

Diese Antwort ist ein In-Place-QuickSort für Python 2.x. Meine Antwort ist eine Interpretation der In-Place-Lösung von Rosetta Code, die auch funktioniert Python 3:

import random

def qsort(xs, fst, lst):
    '''
    Sort the range xs[fst, lst] in-place with vanilla QuickSort

    :param xs:  the list of numbers to sort
    :param fst: the first index from xs to begin sorting from,
                must be in the range [0, len(xs))
    :param lst: the last index from xs to stop sorting at
                must be in the range [fst, len(xs))
    :return:    nothing, the side effect is that xs[fst, lst] is sorted
    '''
    if fst >= lst:
        return

    i, j = fst, lst
    pivot = xs[random.randint(fst, lst)]

    while i <= j:
        while xs[i] < pivot:
            i += 1
        while xs[j] > pivot:
            j -= 1

        if i <= j:
            xs[i], xs[j] = xs[j], xs[i]
            i, j = i + 1, j - 1
    qsort(xs, fst, j)
    qsort(xs, i, lst)

Und wenn Sie bereit sind, auf die In-Place-Eigenschaft zu verzichten, finden Sie unten eine weitere Version, die die Grundideen von Quicksort besser veranschaulicht. Abgesehen von der Lesbarkeit besteht der andere Vorteil darin, dass es stabil ist (gleiche Elemente werden in der sortierten Liste in derselben Reihenfolge angezeigt, die sie früher in der unsortierten Liste hatten). Diese Stabilitätseigenschaft gilt nicht für die oben dargestellte weniger speicherhungrige In-Place-Implementierung.

def qsort(xs):
    if not xs: return xs # empty sequence case
    pivot = xs[random.choice(range(0, len(xs)))]

    head = qsort([x for x in xs if x < pivot])
    tail = qsort([x for x in xs if x > pivot])
    return head + [x for x in xs if x == pivot] + tail
alisianoi
quelle
Vielen Dank, dass Sie diese Lösung geteilt haben. Können Sie uns bitte helfen, die zeitliche Komplexität zu verstehen? Ich sehe, dass die Rekursion es 15 Mal aufruft. Davon sind 8 gültige Aufrufe der Funktion. Bedeutet das, dass die Zeitkomplexität für die erste Lösung O (n) und die Raumkomplexität O (1) als In-Place-Sortierung ist?
ForeverLearner
@Tammy es sieht so aus, als würdest du die Big-O-Notation falsch verstehen. Außerdem verstehe ich Ihre Frage nicht wirklich. Könnten Sie es vielleicht als separate fragen? Schließlich läuft Quicksort als Algorithmus in O (n logn) Zeit und O (n) Raum.
Alisianoi
3
Mein Fehler. Warum um alles in der Welt zählte ich Rekursionen? :-) Nun, 15 Rekursionen sind [1 Aufruf (Level 0) + 2 Aufruf (Level 1 Partition) + 4 Aufruf (Level 2 Partition) + 8 Aufruf (Level 3 Partition oder Leaf Nodes). Wir haben also immer noch eine Höhe von (lg8 + 1) = lgn. Die Gesamtberechnung in jeder Ebene erfolgt für c1 (einige Kosten) * n. Daher O (n lgn). Raumkomplexität für einen Austausch vor Ort = O (1). Daher gilt für n Elemente = O (n). Danke für den Zeiger.
ForeverLearner
3
Dies ist mit Abstand die beste Python-Quicksort im Internet, und es ist traurig zu sehen, dass sie unter so vielen O (n) Space-Lösungen begraben ist :(
Sasha Kondrashov
Danke für die freundlichen Worte @Timofey. Vielleicht möchten Sie einen Blick auf mein Algorithmus-Repo werfen, es hat andere Versionen von Sorten, Graph-Algorithmen usw. usw. github.com/alisianoi/algos-py
alisianoi
23

Quicksort mit Python

Im wirklichen Leben sollten wir immer die von Python bereitgestellte integrierte Sortierung verwenden. Das Verständnis des Quicksort- Algorithmus ist jedoch aufschlussreich.

Mein Ziel hier ist es, das Thema so aufzuschlüsseln, dass es für den Leser leicht verständlich und reproduzierbar ist, ohne auf Referenzmaterialien zurückgreifen zu müssen.

Der Quicksort-Algorithmus ist im Wesentlichen der folgende:

  1. Wählen Sie einen Pivot-Datenpunkt aus.
  2. Verschieben Sie alle Datenpunkte, die kleiner als (unter) dem Drehpunkt sind, an eine Position unterhalb des Drehpunkts. Verschieben Sie diejenigen, die größer oder gleich (über) dem Drehpunkt sind, an eine Position darüber.
  3. Wenden Sie den Algorithmus auf die Bereiche über und unter dem Drehpunkt an

Wenn die Daten zufällig verteilt sind, entspricht die Auswahl des ersten Datenpunkts als Drehpunkt einer zufälligen Auswahl.

Lesbares Beispiel:

Schauen wir uns zunächst ein lesbares Beispiel an, in dem Kommentare und Variablennamen verwendet werden, um auf Zwischenwerte zu verweisen:

def quicksort(xs):
    """Given indexable and slicable iterable, return a sorted list"""
    if xs: # if given list (or tuple) with one ordered item or more: 
        pivot = xs[0]
        # below will be less than:
        below = [i for i in xs[1:] if i < pivot] 
        # above will be greater than or equal to:
        above = [i for i in xs[1:] if i >= pivot]
        return quicksort(below) + [pivot] + quicksort(above)
    else: 
        return xs # empty list

Um den hier gezeigten Algorithmus und Code neu zu formulieren, verschieben wir Werte über dem Drehpunkt nach rechts und Werte unter dem Drehpunkt nach links und übergeben diese Partitionen dann an dieselbe Funktion, um sie weiter zu sortieren.

Golf:

Dies kann auf 88 Zeichen gespielt werden:

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Um zu sehen, wie wir dorthin gelangen, nehmen Sie zuerst unser lesbares Beispiel, entfernen Sie Kommentare und Dokumentzeichenfolgen und suchen Sie den Drehpunkt an Ort und Stelle:

def quicksort(xs):
    if xs: 
        below = [i for i in xs[1:] if i < xs[0]] 
        above = [i for i in xs[1:] if i >= xs[0]]
        return quicksort(below) + [xs[0]] + quicksort(above)
    else: 
        return xs

Finden Sie jetzt unten und oben vor Ort:

def quicksort(xs):
    if xs: 
        return (quicksort([i for i in xs[1:] if i < xs[0]] )
                + [xs[0]] 
                + quicksort([i for i in xs[1:] if i >= xs[0]]))
    else: 
        return xs

andWenn wir nun wissen, dass das vorherige Element zurückgegeben wird, wenn es falsch ist, oder wenn es wahr ist, wertet es das folgende Element aus und gibt es zurück:

def quicksort(xs):
    return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
                   + [xs[0]] 
                   + quicksort([i for i in xs[1:] if i >= xs[0]]))

Da Lambdas einen einzelnen Ausdruck zurückgeben und wir zu einem einzelnen Ausdruck vereinfacht haben (obwohl er unleserlicher wird), können wir jetzt ein Lambda verwenden:

quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
                        + [xs[0]] 
                        + quicksort([i for i in xs[1:] if i >= xs[0]]))

Um auf unser Beispiel zu reduzieren, kürzen Sie die Funktions- und Variablennamen auf einen Buchstaben und entfernen Sie das nicht erforderliche Leerzeichen.

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

Beachten Sie, dass dieses Lambda, wie die meisten Code-Golfer, ein ziemlich schlechter Stil ist.

In-Place-Quicksort mithilfe des Hoare-Partitionierungsschemas

Die vorherige Implementierung erstellt viele unnötige zusätzliche Listen. Wenn wir dies vor Ort tun können, vermeiden wir Platzverschwendung.

Die folgende Implementierung verwendet das Hoare-Partitionierungsschema, über das Sie auf Wikipedia mehr lesen können (aber wir haben anscheinend bis zu 4 redundante Berechnungen pro partition()Aufruf entfernt, indem wir die while-Schleifensemantik anstelle von do-while verwendet und die Verengungsschritte an das Ende von verschoben haben die äußere while-Schleife.).

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low]
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list

Ich bin mir nicht sicher, ob ich es gründlich genug getestet habe:

def main():
    assert quicksort([1]) == [1]
    assert quicksort([1,2]) == [1,2]
    assert quicksort([1,2,3]) == [1,2,3]
    assert quicksort([1,2,3,4]) == [1,2,3,4]
    assert quicksort([2,1,3,4]) == [1,2,3,4]
    assert quicksort([1,3,2,4]) == [1,2,3,4]
    assert quicksort([1,2,4,3]) == [1,2,3,4]
    assert quicksort([2,1,1,1]) == [1,1,1,2]
    assert quicksort([1,2,1,1]) == [1,1,1,2]
    assert quicksort([1,1,2,1]) == [1,1,1,2]
    assert quicksort([1,1,1,2]) == [1,1,1,2]

Fazit

Dieser Algorithmus wird häufig in Informatikkursen gelehrt und in Vorstellungsgesprächen nachgefragt. Es hilft uns, über Rekursion und Teilen und Erobern nachzudenken.

Quicksort ist in Python nicht sehr praktisch, da unser integrierter Timsort- Algorithmus sehr effizient ist und wir Rekursionsgrenzen haben. Wir würden erwarten, Listen an Ort und Stelle zu sortieren list.sortoder neue sortierte Listen mit zu erstellen sorted- beide nehmen ein keyund ein reverseArgument an.

Aaron Hall
quelle
Ihre partitionFunktion scheint nicht richtig zu funktionieren für : partition([5,4,3,2,1], 0, 4). Der erwartete Rückgabeindex ist 4, während er 3 zurückgibt.
matino
@matino Woher kam diese Erwartung? Ich glaube, ich habe den Algorithmus vereinfacht (wie auf Wikipedia beim Schreiben dieser Antwort angegeben), obwohl ich mich irren oder vielleicht weniger effizient sein könnte. Wenn Sie einen Testfall finden könnten, bei dem die gesamte Quicksort-Funktion fehlschlägt, wäre dies hilfreich.
Aaron Hall
@AaronHall, als ich pivot = a_list [high] gewählt habe, aber ich kann einfach nicht herausfinden, wie es dann funktioniert. Kannst du helfen ?
Qiulang
21

Es gibt bereits viele Antworten darauf, aber ich denke, dieser Ansatz ist die sauberste Implementierung:

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    pivots = [x for x in arr if x == arr[0]]
    lesser = quicksort([x for x in arr if x < arr[0]])
    greater = quicksort([x for x in arr if x > arr[0]])

    return lesser + pivots + greater

Sie können natürlich das Speichern von allem in Variablen überspringen und diese sofort wie folgt zurückgeben:

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    return quicksort([x for x in arr if x < arr[0]]) \
        + [x for x in arr if x == arr[0]] \
        + quicksort([x for x in arr if x > arr[0]])
Sebastian Dahlgren
quelle
11
AUF!)? ist das ein 'slowSort'?
Scott 17 理论
3
Ich glaube, im ersten Codebeispiel sollte es "kleiner" und "größer" anstelle von "[kleiner]" und "[größer]" sein - sonst erhalten Sie verschachtelte Listen anstelle einer flachen.
Alice
@Scott 混合 理论 Ich lerne immer noch Zeitkomplexität. Können Sie erläutern, warum diese Implementierung so ist O(N!)? Wenn die verschachtelte Liste angenommen wird [lesser]und [greater]Tippfehler vorliegen, wäre es nicht ein Durchschnitt, O(3N logN)der sich auf den erwarteten Durchschnitt reduzieren würde O(N logN)? Zugegeben, die 3 Listen-Comps machen unnötige Arbeit.
Chrispy
@Chrispy was ist, wenn Sie eine umgekehrte Reihenfolge Liste sortieren, wie 5,4,3,2,1
Scott 28 理论
@Scott 混合 理论 Sie haben Recht, dass die Worst-Case-Laufzeit der schnellen Sortierung langsam ist Θ (n ^ 2), aber laut "Einführung in den Algorithmus" beträgt die durchschnittliche Laufzeit Θ (n lg n). Und, was noch wichtiger ist, die schnelle Sortierung übertrifft in der Praxis im Allgemeinen die Heap-Sortierung
Lungang Fang
6

funktionaler Ansatz:

def qsort(list):
    if len(list) < 2:
        return list

    pivot = list.pop()
    left = filter(lambda x: x <= pivot, list)
    right = filter(lambda x: x > pivot, list)

    return qsort(left) + [pivot] + qsort(right)
akarca
quelle
Die Liste ist in Python 3 reserviert. Die geänderte Version Ihres Codes finden Sie hier: gist.github.com/kunthar/9d8962e1438e93f50dc6dd94d503af3d
Kunthar
akarca und @Kunthar Beide Lösungen in Python2 oder Python3 fügen bei jeder Ausführung ein Element aus der Liste hinzu und zerstören so die Liste. Hier ist eine feste Version: gist.github.com/joshuatvernon/634e0d912401899af0fdc4e23c94192b
joshuatvernon
4

funktionaler Programmieransatz

smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []

print qsort([3,1,4,2,5]) == [1,2,3,4,5]
Arnaldo P. Figueira Figueira
quelle
4

Einfache Implementierung durch Grokking-Algorithmen

def quicksort(arr):
    if len(arr) < 2:
        return arr #base case
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot] 
        more = [i for i in arr[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(more)
Alice
quelle
3

Ich denke, dass beide Antworten hier für die bereitgestellte Liste (die die ursprüngliche Frage beantwortet) in Ordnung sind, aber brechen würden, wenn ein Array mit nicht eindeutigen Werten übergeben wird. Der Vollständigkeit halber möchte ich nur auf den kleinen Fehler in jedem einzelnen hinweisen und erklären, wie man ihn behebt.

Wenn Sie beispielsweise versuchen, das folgende Array [12,4,5,6,7,3,1,15,1] (Beachten Sie, dass 1 zweimal erscheint) mit dem Brionius- Algorithmus zu sortieren, wird irgendwann weniger Array leer sein und das gleiche Array mit einem Wertepaar (1,1), das in der nächsten Iteration nicht getrennt werden kann, und len ()> 1 ... daher erhalten Sie eine Endlosschleife

Sie können das Problem beheben, indem Sie entweder ein Array zurückgeben, wenn weniger leer ist, oder besser, indem Sie nicht sort in Ihrem gleichen Array aufrufen, wie in zangw answer

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)

        # Don't forget to return something!
        return sort(less)+ equal +sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

Die schickere Lösung funktioniert ebenfalls nicht, aber aus einem anderen Grund fehlt die return- Klausel in der Rekursionszeile, die irgendwann dazu führt, dass None zurückgegeben wird und versucht wird, sie an eine Liste anzuhängen.

Um dies zu beheben, fügen Sie dieser Zeile einfach eine Rückkehr hinzu

def qsort(arr): 
   if len(arr) <= 1:
      return arr
   else:
      return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]])
FedeN
quelle
Übrigens hat die prägnante Version weniger Leistung als die lange, da sie das Array im Listenverständnis zweimal wiederholt.
FedeN
3

Dies ist eine Version des Quicksort mit Hoare-Partitionsschema und mit weniger Swaps und lokalen Variablen

def quicksort(array):
    qsort(array, 0, len(array)-1)

def qsort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        qsort(A, lo, p)
        qsort(A, p + 1, hi)

def partition(A, lo, hi):
    pivot = A[lo]
    i, j = lo-1, hi+1
    while True:
      i += 1
      j -= 1
      while(A[i] < pivot): i+= 1
      while(A[j] > pivot ): j-= 1

      if i >= j: 
          return j

      A[i], A[j] = A[j], A[i]


test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)
Madu Alikor
quelle
3

Partition - Teilen Sie ein Array durch einen Drehpunkt, bei dem sich kleinere Elemente nach links und größere Elemente nach rechts bewegen oder umgekehrt. Ein Pivot kann ein zufälliges Element aus einem Array sein. Um diesen Algorithmus zu erstellen, müssen wir wissen, was der Anfangs- und Endindex eines Arrays ist und wo sich ein Pivot befindet. Dann setzen Sie zwei Hilfszeiger L, R.

Wir haben also einen Array-Benutzer [..., begin, ..., end, ...]

Die Startposition der L- und R-Zeiger
[..., begin, next, ..., end, ...]
     R L.

während L <Ende
  1. Wenn ein Benutzer [Pivot]> Benutzer [L], dann R um eins verschieben und Benutzer [R] mit Benutzer [L] tauschen.
  2. L um eins verschieben

Nach dem Austausch von Benutzer [R] mit Benutzer [Pivot]

Schnelle Sortierung - Verwenden Sie den Partitionsalgorithmus, bis jeder nächste Teil der Teilung durch einen Pivot einen Anfangsindex aufweist, der größer oder gleich dem Endindex ist.

def qsort(user, begin, end):

    if begin >= end:
        return

    # partition
    # pivot = begin
    L = begin+1
    R = begin
    while L < end:
        if user[begin] > user[L]:
            R+=1
            user[R], user[L] = user[L], user[R]
        L+= 1
    user[R], user[begin] = user[begin], user[R]

    qsort(user, 0, R)
    qsort(user, R+1, end)

tests = [
    {'sample':[1],'answer':[1]},
    {'sample':[3,9],'answer':[3,9]},
    {'sample':[1,8,1],'answer':[1,1,8]},
    {'sample':[7,5,5,1],'answer':[1,5,5,7]},
    {'sample':[4,10,5,9,3],'answer':[3,4,5,9,10]},
    {'sample':[6,6,3,8,7,7],'answer':[3,6,6,7,7,8]},
    {'sample':[3,6,7,2,4,5,4],'answer':[2,3,4,4,5,6,7]},
    {'sample':[1,5,6,1,9,0,7,4],'answer':[0,1,1,4,5,6,7,9]},
    {'sample':[0,9,5,2,2,5,8,3,8],'answer':[0,2,2,3,5,5,8,8,9]},
    {'sample':[2,5,3,3,2,0,9,0,0,7],'answer':[0,0,0,2,2,3,3,5,7,9]}
]

for test in tests:

    sample = test['sample'][:]
    answer = test['answer']

    qsort(sample,0,len(sample))

    print(sample == answer)
Grzegorz Eleryk
quelle
Bitte erläutern Sie Ihren Code / Ihre Ergänzungen, damit OP und zukünftige Ansichten mehr davon profitieren können.
Omar Einea
2

Oder wenn Sie einen Einzeiler bevorzugen, der auch das Python-Äquivalent von C / C ++ - Varags, Lambda-Ausdrücken und if-Ausdrücken veranschaulicht:

qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])
Bruce Lucas
quelle
2
def quick_sort(self, nums):
    def helper(arr):
        if len(arr) <= 1: return arr
        #lwall is the index of the first element euqal to pivot
        #rwall is the index of the first element greater than pivot
        #so arr[lwall:rwall] is exactly the middle part equal to pivot after one round
        lwall, rwall, pivot = 0, 0, 0
        #choose rightmost as pivot
        pivot = arr[-1]
        for i, e in enumerate(arr):
            if e < pivot:
                #when element is less than pivot, shift the whole middle part to the right by 1
                arr[i], arr[lwall] = arr[lwall], arr[i]
                lwall += 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e == pivot:
                #when element equals to pivot, middle part should increase by 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e > pivot: continue
        return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:])
    return helper(nums)
MoeChen
quelle
2

Ich weiß, dass viele Leute diese Frage richtig beantwortet haben und ich habe es genossen, sie zu lesen. Meine Antwort ist fast die gleiche wie die von zangw, aber ich denke, die vorherigen Mitwirkenden haben nicht gut visuell erklärt, wie die Dinge tatsächlich funktionieren. Hier ist mein Versuch, anderen zu helfen, die diese Frage / Antwort in Zukunft zu einem Thema besuchen könnten einfache Lösung für die QuickSort-Implementierung.

Wie funktioniert es ?

  1. Grundsätzlich wählen wir das erste Element als Dreh- und Angelpunkt aus unserer Liste aus und erstellen dann zwei Unterlisten.
  2. Unsere erste Unterliste enthält die Elemente, die weniger als Pivot sind
  3. Unsere zweite Unterliste enthält unsere Artikel, die größer oder gleich Pivot sind
  4. Wir sortieren diese dann schnell und kombinieren sie mit der ersten Gruppe + Pivot + der zweiten Gruppe, um das Endergebnis zu erhalten.

Hier ist ein Beispiel zusammen mit Visual dazu ... (Pivot) 9,11,2,0

Durchschnitt: n log von n

schlimmster Fall: n ^ 2

Geben Sie hier die Bildbeschreibung ein

Der Code:

def quicksort(data):
if (len(data) < 2):
    return data
else:
    pivot = data[0]  # pivot
    #starting from element 1 to the end
    rest = data[1:]
    low = [each for each in rest if each < pivot]
    high = [each for each in rest if each >= pivot]
    return quicksort(low) + [pivot] + quicksort(high)

items = [9,11,2,0] print (Quicksort (Artikel))

grepit
quelle
1
def quick_sort(array):
    return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] \
        + quick_sort([x for x in array[1:] if x >= array[0]]) if array else []
Dapangmao
quelle
1
def Partition(A,p,q):
    i=p
    x=A[i]
    for j in range(p+1,q+1):
        if A[j]<=x:
            i=i+1
            tmp=A[j]
            A[j]=A[i]
            A[i]=tmp
    l=A[p]
    A[p]=A[i]
    A[i]=l
    return i

def quickSort(A,p,q):
    if p<q:
        r=Partition(A,p,q)
        quickSort(A,p,r-1)
        quickSort(A,r+1,q)
    return A
Amy
quelle
1
Bitte erläutern Sie, was Ihr Code tut und wie er die Frage beantwortet. Insbesondere in welcher Beziehung steht es zu dem in der Frage angegebenen Code. Die Antwort sollte dem OP und zukünftigen Besuchern Anleitungen zum Debuggen und Beheben ihres Problems geben. Wenn Sie darauf hinweisen, welche Idee hinter Ihrem Code steckt, können Sie das Problem besser verstehen und Ihre Lösung anwenden oder ändern. Stack Overflow ist kein Code-Schreibdienst, sondern ein Lehr- und Lernort.
Palec
1

Eine "echte" In-Place-Implementierung [Algorithmen 8.9, 8.11 aus dem Algorithm Design and Applications Book von Michael T. Goodrich und Roberto Tamassia]:

from random import randint

def partition (A, a, b):
    p = randint(a,b)
    # or mid point
    # p = (a + b) / 2

    piv = A[p]

    # swap the pivot with the end of the array
    A[p] = A[b]
    A[b] = piv

    i = a     # left index (right movement ->)
    j = b - 1 # right index (left movement <-)

    while i <= j:
        # move right if smaller/eq than/to piv
        while A[i] <= piv and i <= j:
            i += 1
        # move left if greater/eq than/to piv
        while A[j] >= piv and j >= i:
            j -= 1

        # indices stopped moving:
        if i < j:
            # swap
            t = A[i]
            A[i] = A[j]
            A[j] = t
    # place pivot back in the right place
    # all values < pivot are to its left and 
    # all values > pivot are to its right
    A[b] = A[i]
    A[i] = piv

    return i

def IpQuickSort (A, a, b):

    while a < b:
        p = partition(A, a, b) # p is pivot's location

        #sort the smaller partition
        if p - a < b - p:
            IpQuickSort(A,a,p-1)
            a = p + 1 # partition less than p is sorted
        else:
            IpQuickSort(A,p+1,b)
            b = p - 1 # partition greater than p is sorted


def main():
    A =  [12,3,5,4,7,3,1,3]
    print A
    IpQuickSort(A,0,len(A)-1)
    print A

if __name__ == "__main__": main()
anask
quelle
1

Der Algorithmus besteht aus 4 einfachen Schritten:

  1. Teilen Sie das Array in 3 verschiedene Teile: links, Pivot und rechts, wobei Pivot nur ein Element enthält. Wählen wir dieses Pivot-Element als erstes Element des Arrays
  2. Fügen Sie dem jeweiligen Teil Elemente hinzu, indem Sie sie mit dem Pivot-Element vergleichen. (Erklärung in Kommentaren)
  3. Verwenden Sie diesen Algorithmus erneut, bis alle Elemente im Array sortiert wurden
  4. Zum Schluss verbinden Sie die Teile links + Drehpunkt + rechts

Code für den Algorithmus in Python:

def my_sort(A):

      p=A[0]                                       #determine pivot element. 
      left=[]                                      #create left array
      right=[]                                     #create right array
      for i in range(1,len(A)):
        #if cur elem is less than pivot, add elem in left array
        if A[i]< p:
          left.append(A[i])         
          #the recurssion will occur only if the left array is atleast half the size of original array
          if len(left)>1 and len(left)>=len(A)//2:          
              left=my_sort(left)                            #recursive call
        elif A[i]>p: 
          right.append(A[i])                                #if elem is greater than pivot, append it to right array
          if len(right)>1 and len(right)>=len(A)//2:        # recurssion will occur only if length of right array is atleast the size of original array
              right=my_sort(right)
     A=left+[p]+right                                        #append all three part of the array into one and return it
     return A

my_sort([12,4,5,6,7,3,1,15])

Fahren Sie mit diesem Algorithmus rekursiv mit dem linken und rechten Teil fort.

Mamta Kanvinde
quelle
1

Eine weitere QuickSort-Implementierung:

# A = Array 
# s = start index
# e = end index
# p = pivot index
# g = greater than pivot boundary index

def swap(A,i1,i2):
  A[i1], A[i2] = A[i2], A[i1]

def partition(A,g,p):
    # O(n) - just one for loop that visits each element once
    for j in range(g,p):
      if A[j] <= A[p]:
        swap(A,j,g)
        g += 1

    swap(A,p,g)
    return g

def _quicksort(A,s,e):
    # Base case - we are sorting an array of size 1
    if s >= e:
      return

    # Partition current array
    p = partition(A,s,e)
    _quicksort(A,s,p-1) # Left side of pivot
    _quicksort(A,p+1,e) # Right side of pivot

# Wrapper function for the recursive one
def quicksort(A):
    _quicksort(A,0,len(A)-1)

A = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,-1]

print(A)
quicksort(A)
print(A)
Gillespie
quelle
1

Für Version Python 3.x : Ein Funktionsmodul operator, das hauptsächlich zur Verbesserung der Lesbarkeit verwendet wird.

from operator import ge as greater, lt as lesser

def qsort(L): 
    if len(L) <= 1: return L
    pivot   = L[0]
    sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]

    return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))

und wird getestet als

print (qsort([3,1,4,2,5]) == [1,2,3,4,5])
Lebensbalance
quelle
Schön (was den undokumentierten Code betrifft ), wenn auch ähnlich wie die von acarca , Arnaldo P. Figueira Figueiras und Birgers Antworten aus vergangenen Jahren. Ich bin mir nicht sicher, ob dies eine Antwort ist, wenn die Frage lautet … complete my code?. Die Verwendung lambdazum Definieren sublist()ist nicht unbedingt erforderlich.
Graubart
@greybeard Eigentlich wurde Arnaldos Code in Python 3 nicht kompiliert. Wie kann er sublistauch nur mit definiert werden filter? Ist das überhaupt möglich?
Lebensbalance
1
(Vorübergehender Kommentar: Denken Sie an def- haben Sie noch nicht angefangen zu basteln, da ich herausfinden möchte , ob es eine effizientere Möglichkeit gibt, die Elemente einer iterierbaren Datei auf separate Listen zu verteilen (oder alternativ eine Liste mit einer). Kategorie "nach dem anderen).)
Graubart
1

Hier ist eine einfache Implementierung: -

def quicksort(array):
            if len(array) < 2:
                  return array
            else:
                  pivot= array[0]
                  less = [i for i in array[1:] if i <= pivot]

                  greater = [i for i in array[1:] if i > pivot]

                  return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))
abhishek4996
quelle
1

Der Algorithmus enthält zwei Grenzen, von denen eine Elemente kleiner als der Drehpunkt (verfolgt durch den Index "j") und die andere Elemente größer als der Drehpunkt (verfolgt durch den Index "i") hat.

In jeder Iteration wird ein neues Element durch Inkrementieren von j verarbeitet.

Invariante: -

  1. Alle Elemente zwischen Pivot und i sind kleiner als der Pivot und
  2. Alle Elemente zwischen i und j sind größer als der Drehpunkt.

Wenn die Invariante verletzt wird, werden das i-te und das j-te Element vertauscht und i wird inkrementiert.

Nachdem alle Elemente verarbeitet wurden und alles, nachdem der Pivot partitioniert wurde, wird das Pivot-Element gegen das letzte kleinere Element ausgetauscht.

Das Pivot-Element befindet sich nun an der richtigen Stelle in der Sequenz. Die Elemente davor sind kleiner als sie und die Elemente danach sind größer als sie und sie sind unsortiert.

def quicksort(sequence, low, high):
    if low < high:    
        pivot = partition(sequence, low, high)
        quicksort(sequence, low, pivot - 1)
        quicksort(sequence, pivot + 1, high)

def partition(sequence, low, high):
    pivot = sequence[low]
    i = low + 1
    for j in range(low + 1, high + 1):
        if sequence[j] < pivot:
            sequence[j], sequence[i] = sequence[i], sequence[j]
            i += 1
    sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
    return i - 1

def main(sequence):
    quicksort(sequence, 0, len(sequence) - 1)
    return sequence

if __name__ == '__main__':
    sequence = [-2, 0, 32, 1, 56, 99, -4]
    print(main(sequence))

Pivot auswählen

Ein "guter" Pivot führt zu zwei Teilsequenzen von ungefähr derselben Größe. Deterministisch kann ein Pivot-Element entweder auf naive Weise oder durch Berechnung des Medians der Sequenz ausgewählt werden.

Eine naive Implementierung der Auswahl eines Pivots ist das erste oder letzte Element. Die Laufzeit im ungünstigsten Fall ist in diesem Fall, wenn die Eingabesequenz bereits sortiert oder umgekehrt sortiert ist, da eine der Teilsequenzen leer ist und nur ein Element pro rekursivem Aufruf entfernt wird.

Eine perfekt ausbalancierte Aufteilung wird erreicht, wenn der Drehpunkt das Medianelement der Sequenz ist. Es gibt eine gleiche Anzahl von Elementen, die größer als es und kleiner als es sind. Dieser Ansatz garantiert eine bessere Gesamtlaufzeit, ist jedoch viel zeitaufwändiger.

Eine nicht deterministische / zufällige Art der Auswahl des Drehpunkts wäre die gleichmäßige zufällige Auswahl eines Elements. Dies ist ein einfacher und leichter Ansatz, der das Worst-Case-Szenario minimiert und auch zu einer grob ausgewogenen Aufteilung führt. Dies wird auch ein Gleichgewicht zwischen dem naiven Ansatz und dem mittleren Ansatz bei der Auswahl des Pivots herstellen.


quelle
0
  1. Zuerst deklarieren wir den ersten Wert im Array als pivot_value und setzen auch die linke und rechte Markierung
  2. Wir erstellen die erste while-Schleife. Diese while-Schleife weist den Partitionsprozess an, erneut ausgeführt zu werden, wenn er die erforderliche Bedingung nicht erfüllt
  3. dann wenden wir den Partitionsprozess an
  4. Nachdem beide Partitionsprozesse ausgeführt wurden, prüfen wir, ob sie die richtige Bedingung erfüllen. Wenn dies der Fall ist, markieren wir es als erledigt. Wenn nicht, wechseln wir den linken und rechten Wert und wenden es erneut an
  5. Sobald dies erledigt ist, wechseln Sie den linken und rechten Wert und geben Sie den split_point zurück

Ich füge den Code unten hinzu! Diese Quicksortierung ist aufgrund der Position des Pivot-Werts ein großartiges Lernwerkzeug . Da es sich an einem konstanten Ort befindet, können Sie es mehrmals durchlaufen und sich ein Bild davon machen, wie alles funktioniert. In der Praxis ist es am besten, den Pivot zufällig zu sortieren, um eine O (N ^ 2) -Laufzeit zu vermeiden.

def quicksort10(alist):
    quicksort_helper10(alist, 0, len(alist)-1)

def quicksort_helper10(alist, first, last):
    """  """
    if first < last:
        split_point = partition10(alist, first, last)
        quicksort_helper10(alist, first, split_point - 1)
        quicksort_helper10(alist, split_point + 1, last)

def partition10(alist, first, last):
    done = False
    pivot_value = alist[first]
    leftmark = first + 1
    rightmark = last
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivot_value:
            leftmark = leftmark + 1
        while leftmark <= rightmark and alist[rightmark] >= pivot_value:
            rightmark = rightmark - 1

        if leftmark > rightmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp
    return rightmark
DanHabib
quelle
0
def quick_sort(l):
    if len(l) == 0:
        return l
    pivot = l[0]
    pivots = [x for x in l if x == pivot]
    smaller = quick_sort([x for x in l if x < pivot])
    larger = quick_sort([x for x in l if x > pivot])
    return smaller + pivots + larger
feroz
quelle
18 weitere Antworten, von denen mehr als die Hälfte die ursprüngliche Frage von OP zum Thema "Verketten der drei Arrays" beantworten. Fügt Ihre Antwort etwas Neues hinzu?
Teepeemm
0

Vollständiges Beispiel mit gedruckten Variablen im Partitionsschritt:

def partition(data, p, right):
    print("\n==> Enter partition: p={}, right={}".format(p, right))
    pivot = data[right]
    print("pivot = data[{}] = {}".format(right, pivot))

    i = p - 1  # this is a dangerous line

    for j in range(p, right):
        print("j: {}".format(j))
        if data[j] <= pivot:
            i = i + 1
            print("new i: {}".format(i))
            print("swap: {} <-> {}".format(data[i], data[j]))
            data[i], data[j] = data[j], data[i]

    print("swap2: {} <-> {}".format(data[i + 1], data[right]))
    data[i + 1], data[right] = data[right], data[i + 1]
    return i + 1


def quick_sort(data, left, right):
    if left < right:
        pivot = partition(data, left, right)
        quick_sort(data, left, pivot - 1)
        quick_sort(data, pivot + 1, right)

data = [2, 8, 7, 1, 3, 5, 6, 4]

print("Input array: {}".format(data))
quick_sort(data, 0, len(data) - 1)
print("Output array: {}".format(data))
Andrei Sura
quelle
0
def is_sorted(arr): #check if array is sorted
    for i in range(len(arr) - 2):
        if arr[i] > arr[i + 1]:
            return False
    return True

def qsort_in_place(arr, left, right): #arr - given array, #left - first element index, #right - last element index
    if right - left < 1: #if we have empty or one element array - nothing to do
        return
    else:
        left_point = left #set left pointer that points on element that is candidate to swap with element under right pointer or pivot element
        right_point = right - 1 #set right pointer that is candidate to swap with element under left pointer

        while left_point <= right_point: #while we have not checked all elements in the given array
            swap_left = arr[left_point] >= arr[right] #True if we have to move that element after pivot
            swap_right = arr[right_point] < arr[right] #True if we have to move that element before pivot

            if swap_left and swap_right: #if both True we can swap elements under left and right pointers
                arr[right_point], arr[left_point] = arr[left_point], arr[right_point]
                left_point += 1
                right_point -= 1
            else: #if only one True we don`t have place for to swap it
                if not swap_left: #if we dont need to swap it we move to next element
                    left_point += 1
                if not swap_right: #if we dont need to swap it we move to prev element
                    right_point -= 1

        arr[left_point], arr[right] = arr[right], arr[left_point] #swap left element with pivot

        qsort_in_place(arr, left, left_point - 1) #execute qsort for left part of array (elements less than pivot)
        qsort_in_place(arr, left_point + 1, right) #execute qsort for right part of array (elements most than pivot)

def main():
    import random
    arr = random.sample(range(1, 4000), 10) #generate random array
    print(arr)
    print(is_sorted(arr))
    qsort_in_place(arr, 0, len(arr) - 1)
    print(arr)
    print(is_sorted(arr))

if __name__ == "__main__":
    main()
Igor Mansurov
quelle
1
Bitte geben Sie eine Erklärung
Rai
0

Dieser Algorithmus verwendet keine rekursiven Funktionen.

Sei Neine beliebige Liste von Zahlen mit len(N) > 0. Set K = [N]und das folgende Programm ausführen.

Hinweis: Dies ist ein stabiler Sortieralgorithmus.

def BinaryRip2Singletons(K, S):
    K_L = []
    K_P = [ [K[0][0]] ] 
    K_R = []
    for i in range(1, len(K[0])):
        if   K[0][i] < K[0][0]:
            K_L.append(K[0][i])
        elif K[0][i] > K[0][0]:
            K_R.append(K[0][i])
        else:
            K_P.append( [K[0][i]] )
    K_new = [K_L]*bool(len(K_L)) + K_P + [K_R]*bool(len(K_R)) + K[1:]
    while len(K_new) > 0:
        if len(K_new[0]) == 1:
            S.append(K_new[0][0])
            K_new = K_new[1:]
        else: 
            break
    return K_new, S

N = [16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]
K = [ N ]
S = []

print('K =', K, 'S =', S)
while len(K) > 0:
    K, S = BinaryRip2Singletons(K, S)
    print('K =', K, 'S =', S)

PROGRAMMAUSGABE:

K = [[16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]] S = []
K = [[11, 15, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1], [16], [16], [19]] S = []
K = [[10, 4, 10, 5, 2, 3, 4, 7, 1], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[4, 5, 2, 3, 4, 7, 1], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[2, 3, 1], [4], [4], [5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4]
K = [[15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [[12, 14], [15], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11, 12, 14, 15, 16, 16, 19]
CopyPasteIt
quelle
0

Wahrscheinlich nur eine Präferenzsache, aber ich möchte die Validierung an die Spitze meiner Funktionen setzen.

def quicksort(arr):
  if len(arr) <= 1:
    return arr

  left  = []
  right = []
  equal = []
  pivot = arr[-1]
  for num in arr:
    if num < pivot:
      left.append(num)
    elif num == pivot:
      equal.append(num)
    else:
      right.append(num)

  return quicksort(left) + equal + quicksort(right)
Robo Rick
quelle
0

Meine Antwort ist der großen von @alisianoi sehr ähnlich. Ich glaube jedoch, dass sein Code eine leichte Ineffizienz aufweist (siehe meinen Kommentar), den ich entfernt habe. Darüber hinaus habe ich weitere Erklärungen hinzugefügt und war etwas spezifischer in Bezug auf das Problem doppelter (Pivot-) Werte.

def quicksort(nums, begin=0, end=None):
    # Only at the beginning end=None. In this case set to len(nums)-1
    if end is None: end = len(nums) - 1

    # If list part is invalid or has only 1 element, do nothing
    if begin>=end: return

    # Pick random pivot
    pivot = nums[random.randint(begin, end)]

    # Initialize left and right pointers
    left, right = begin, end
    while left < right:
        # Find first "wrong" value from left hand side, i.e. first value >= pivot
        # Find first "wrong" value from right hand side, i.e. first value <= pivot
        # Note: In the LAST while loop, both left and right will point to pivot!
        while nums[left] < pivot: left += 1
        while nums[right] > pivot: right -= 1

        # Swap the "wrong" values
        if left != right:
            nums[left], nums[right] = nums[right], nums[left]
            # Problem:  loop can get stuck if pivot value exists more than once. Simply solve with...
            if nums[left] == nums[right]:
                assert nums[left]==pivot
                left += 1

    # Now, left and right both point to a pivot value.
    # All values to its left are smaller (or equal in case of duplicate pivot values)
    # All values to its right are larger.
    assert left == right and nums[left] == pivot
    quicksort(nums, begin, left - 1)
    quicksort(nums, left + 1, end)
    return
gebbissimo
quelle