wake-up-neo.com

Quicksort mit Python

Ich bin völlig neu in Python und ich versuche, Quicksort darin zu implementieren.

Ich weiß nicht, wie man die drei Arrays verkettet und druckt. 

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)
73
user2687481
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)
            Elif x == pivot:
                equal.append(x)
            else 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
187
Brionius

Schnelle Sortierung ohne zusätzlichen Speicher (an Ort und Stelle)

Verwendungszweck:

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)
118
suquant

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 von Array _arr[0]_ als Pivot aus

    _[arr[0]]_

  2. qsort die Elemente des Arrays, die kleiner sind als Pivot mit 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]])

67
zangw

Wenn ich in Google nach "Python-Quicksort-Implementierung" suche, wird diese Frage als erstes Ergebnis angezeigt. Ich verstehe, dass die anfängliche Frage darin bestand "zu helfen, den Code zu korrigieren", aber es gibt bereits viele Antworten, die diese Anfrage ignorieren: die aktuell zweithäufigste gewählte , die schreckliche Einzeiler mit der komische "You are fired" -Kommentar und im Allgemeinen viele Implementierungen, die nicht vorhanden sind (dh zusätzlichen Speicher verwenden, der der Eingangslistengröße proportional ist). Diese Antwort bietet eine In-Place-Lösung, jedoch für python 2.x. Im Folgenden folgt meine Interpretation der In-Place-Lösung aus Rosetta Code , die auch für python 3 gut funktioniert:

import random

def qsort(l, fst, lst):
    if fst >= lst: return

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

    while i <= j:
        while l[i] < pivot: i += 1
        while l[j] > pivot: j -= 1
        if i <= j:
            l[i], l[j] = l[j], l[i]
            i, j = i + 1, j - 1
    qsort(l, fst, j)
    qsort(l, i, lst)

Und wenn Sie bereit sind, auf die In-Place-Eigenschaft zu verzichten, finden Sie unten eine weitere Version, die die Grundgedanken von quicksort besser veranschaulicht. Abgesehen von der Lesbarkeit besteht der weitere Vorteil darin, dass es stable ist (gleiche Elemente erscheinen in der sortierten Liste in derselben Reihenfolge wie in der unsortierten Liste). Diese Stabilitätseigenschaft gilt nicht für die oben präsentierte weniger speicherintensive In-Place-Implementierung.

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

    head = qsort([elem for elem in l if elem < pivot])
    tail = qsort([elem for elem in l if elem > pivot])
    return head + [elem for elem in l if elem == pivot] + tail
28
alisianoi

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 aller Variablen überspringen und 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]])
22

Quicksort mit Python

Im wirklichen Leben sollten wir immer die eingebaute Sortierung von Python 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 nachvollziehbar ist, ohne zu Referenzmaterialien zurückkehren zu müssen.

Der Quicksort-Algorithmus ist im Wesentlichen der folgende:

  1. Wählen Sie einen Pivot-Datenpunkt aus.
  2. Bewegen Sie alle Datenpunkte unterhalb (unterhalb) des Pivots in eine Position unterhalb des Pivots. Bewegen Sie diejenigen Punkte, die größer oder gleich (Pivot) des Pivots sind, in eine darüber liegende Position.
  3. Wenden Sie den Algorithmus auf die Bereiche oberhalb und unterhalb des Pivots an

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

Lesbares Beispiel:

Sehen wir uns zunächst ein lesbares Beispiel an, in dem Kommentare und Variablennamen auf Zwischenwerte 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 vorgestellten Algorithmus und Code neu zu formulieren, verschieben wir Werte oberhalb des Drehpunkts nach rechts und Werte unterhalb des Drehpunkts nach links und übergeben diese Partitionen an dieselbe Funktion, um weiter sortiert zu werden.

Golf gespielt:

Hier können bis zu 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 Docstrings und suchen Sie den Drehpunkt vor Ort:

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

Jetzt unten und oben finden:

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

Nun, da wir wissen, dass and das vorherige Element bei false zurückgibt, wertet es andernfalls das folgende Element aus und gibt dieses 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 eine einzige Epression zurückgeben und wir uns zu einem einzigen Ausdruck vereinfacht haben (obwohl der Ausdruck immer unlesbarer 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 es auf unser Beispiel zu reduzieren, kürzen Sie die Funktions- und Variablennamen auf einen Buchstaben und entfernen Sie den nicht benötigten Leerraum.

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 das meiste Code-Golf, ziemlich schlecht ist.

Direkter Quicksort mit dem Hoare-Partitionierungsschema

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

In der folgenden Implementierung wird das Hoare-Partitionierungsschema verwendet, das Sie lesen Sie mehr über Wikipedia (jedoch haben wir anscheinend bis zu 4 redundante Berechnungen pro partition()-Aufruf entfernt, indem Sie die while-loop-Semantik anstelle von do-while und moving verwenden die Verengung geht bis zum Ende der äußeren 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

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 unterrichtet und in Vorstellungsgesprächen abgefragt. Es hilft uns, über Rekursion nachzudenken und zu teilen und zu erobern. 

Quicksort ist in Python nicht sehr praktisch, da unser eingebauter Timsort -Algorithmus ziemlich effizient ist und wir Rekursionsgrenzen haben. Es wäre zu erwarten, dass Sie die Listen direkt mit list.sort sortieren oder neue sortierte Listen mit sorted erstellen. Beide verwenden ein key- und ein reverse-Argument. 

16
Aaron Hall

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)
6
akarca

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]

Ich denke, dass beide Antworten hier für die bereitgestellte Liste in Ordnung sind (was die ursprüngliche Frage beantwortet), würden aber kaputt gehen, wenn ein Array mit nicht eindeutigen Werten übergeben wird. Der Vollständigkeit halber möchte ich nur auf den kleinen Fehler hinweisen und ihnen erklären, wie sie behoben werden können.

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 dies irgendwann mit Das Array less ist leer und das Array equal mit einem Wertepaar (1,1), das bei der nächsten Iteration nicht getrennt werden kann, und len ()> 1 ... daher Sie werden mit einer Endlosschleife enden

Sie können das Problem beheben, indem Sie entweder array zurückgeben, wenn less leer ist, oder besser durch not Sortierung in Ihrem gleichwertigen Array, 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 Züchterlösung bricht ebenfalls ab, aber aus einem anderen Grund fehlt die return -Klausel in der Rekursionszeile, was irgendwann dazu führen wird, dass None zurückgegeben wird, und versucht, sie an eine Liste anzuhängen.

Um dies zu beheben, fügen Sie einfach eine Zeile zu dieser Zeile 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]])
3
FedeN

Trennwand - Teilen Sie ein Array durch einen Drehpunkt, um den kleinere Elemente nach links und die größeren Elemente nach rechts oder umgekehrt verschoben werden. Ein Drehpunkt kann ein zufälliges Element eines Arrays sein. Um diesen Algorithmus zu erstellen, müssen wir wissen, was Anfang und Ende eines Arrays sind und wo sich ein Pivot befindet. Stellen Sie dann zwei Hilfszeiger L, R ein.

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] ist, bewegen Sie R um eins und tauschen Sie Benutzer [R] mit Benutzer [L] aus.
2. L um eins bewegen

Nach dem Tauschen des Benutzers [R] mit dem Benutzer [Pivot]

Schnelle Sorte - Verwenden Sie den Partitionsalgorithmus, bis jeder nächste Teil der Aufteilung durch einen Pivot einen Anfangsindex hat, 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)
2
Grzegorz Eleryk
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
1
Amy

Der Algorithmus enthält zwei Grenzen, von denen eine Elemente weniger als der Drehpunkt (verfolgt durch den Index "j") und die andere Elemente größere Elemente 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 die Elemente ith und jth ausgetauscht, und i Wird inkrementiert. 

Nachdem alle Elemente verarbeitet wurden und alles, nachdem der Drehpunkt .__ unterteilt wurde, wird das Schwenkelement gegen das letzte Element Getauscht, das kleiner ist.

Das Schwenkelement befindet sich nun an der richtigen Stelle in der Reihenfolge. Die -Elemente davor werden weniger sein als die, und die Elemente danach werden Größer sein als sie, und sie werden 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 __== '__main__':
    sequence = [-2, 0, 32, 1, 56, 99, -4]
    print(main(sequence))

Einen Drehpunkt auswählen

Ein "guter" Pivot führt zu zwei Teilsequenzen, die in etwa die gleiche Größe haben. Deterministisch kann ein Pivotelement entweder auf naive Weise oder durch Berechnen 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 dann der Fall, wenn die Eingangssequenz Bereits sortiert oder rückwärts sortiert ist, da eine der Untersequenzen Leer ist. Dadurch wird nur ein Element pro rekursiven Aufruf von____ entfernt .

Ein perfekt ausbalancierter Split wird erreicht, wenn der Pivot das Medianelement der Sequenz ist. Es gibt eine gleiche Anzahl von Elementen, die größer als __ und kleiner sind. Dieser Ansatz garantiert insgesamt eine bessere Laufzeit, ist jedoch viel zeitaufwändiger.

Ein nicht deterministischer/zufälliger Weg zum Auswählen des Drehpunkts würde darin bestehen, ein Element zufällig gleichförmig auszuwählen. Dies ist eine einfache und leichtgewichtige .__-Methode, die das Worst-Case-Szenario minimiert und auch zu einem __-ausgeglichenen Split führt. Dies wird auch ein Gleichgewicht zwischen dem naiven Ansatz und dem mittleren Ansatz zur Auswahl des Pivots bieten.

1
SR8H

Der Algorithmus besteht aus 4 einfachen Schritten:

  1. Unterteilen Sie das Array in 3 verschiedene Teile: links, rechts und links, wobei der Drehpunkt nur ein Element hat. Wir wählen dieses Pivot-Element als erstes Array-Element
  2. Fügen Sie dem jeweiligen Teil Elemente hinzu, indem Sie sie mit dem Schwenkelement vergleichen. (Erklärung in Kommentaren)
  3. Rekursieren Sie diesen Algorithmus, bis alle Elemente im Array sortiert wurden
  4. Zum Schluss füge links + Pivot + rechte Teile zusammen

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.

1
Mamta Kanvinde

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

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])
1
lifebalance

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)
1
Gillespie

Einfache Implementierung von 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)
1
Alice

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])
1
Bruce Lucas

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 bei zangw, aber ich denke, die vorherigen Mitwirkenden haben es nicht gut gemacht, visuell zu erklären, wie die Dinge tatsächlich funktionieren ... einfache lösung für die quicksort-implementierung.

Wie funktioniert es ?

  1. Grundsätzlich wählen wir das erste Element als Drehpunkt 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 dem Pivot sind
  4. Wir sortieren dann schnell alle und kombinieren die erste Gruppe + Pivot + die zweite Gruppe, um das Endergebnis zu erhalten.

Hier ist ein Beispiel zusammen mit Visual, um dazu zu gehören ....__ (Pivot) 9,11,2,0

durchschnitt: n log von n 

schlimmerer Fall: n ^ 2 

 enter image description here

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 (items))

1
grepit

Dies ist eine Version des Quicksort mit Hoare-Partitionsschema und 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)
1
Madu Alikor
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 []
1
dapangmao
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)
1
MoeChen

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 __== "__main__": main()
1
anask

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]))
0
abhishek4996

Dieser Algorithmus verwendet keine rekursiven Funktionen.

Sei N eine beliebige Liste von Zahlen mit len(N) > 0. Setzen Sie K = [N] und führen Sie das folgende Programm aus.

Hinweis: Dies ist ein Stable 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]
0
CopyPasteIt

Vollständiges Beispiel mit gedruckten Variablen beim 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))
0
Andrei Sura
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
0
feroz
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 __== "__main__":
    main()
0
Igor Mansurov
  1. Zuerst deklarieren wir den ersten Wert im Array als Pivot_value und setzen außerdem die linken und rechten Markierungen
  2. Wir erstellen die erste while-Schleife. Diese while-Schleife gibt an, dass der Partitionsprozess erneut ausgeführt werden soll, wenn er die erforderliche Bedingung nicht erfüllt
  3. dann wenden wir den Partitionsprozess an
  4. nachdem beide Partitionierungsprozesse ausgeführt wurden, überprüfen wir, ob die ordnungsgemäße Bedingung erfüllt. Wenn dies der Fall ist, markieren wir es als erledigt. Wenn dies nicht der Fall ist, werden die linken und rechten Werte geändert und erneut angewendet
  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 bei! Dieses Quicksort ist ein hervorragendes Lernwerkzeug, da Position des Pivotwerts . Da es an einem konstanten Ort ist, können Sie es mehrmals durchlaufen und wirklich einen Eindruck davon bekommen, wie alles funktioniert. In der Praxis ist es am besten, den Pivot zufällig zu sortieren, um die Laufzeit von O (N ^ 2) 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
0
DanHabib
# 编程珠玑实现
# 双向排序: 提高非随机输入的性能
# 不需要额外的空间,在待排序数组本身内部进行排序
# 基准值通过random随机选取
# 入参: 待排序数组, 数组开始索引 0, 数组结束索引 len(array)-1
import random

def swap(arr, l, u):
    arr[l],arr[u] = arr[u],arr[l]
    return arr

def QuickSort_Perl(arr, l, u):
    # 小数组排序i可以用插入或选择排序 
    # if u-l < 50 : return arr
    # 基线条件: low index = upper index; 也就是只有一个值的区间
    if l >= u:
        return arr
    # 随机选取基准值, 并将基准值替换到数组第一个元素        
    swap(arr, l, int(random.uniform(l, u)))
    temp = arr[l]
    # 缓存边界值, 从上下边界同时排序
    i, j = l, u
    while True:
        # 第一个元素是基准值,所以要跳过
        i+=1
        # 在小区间中, 进行排序
        # 从下边界开始寻找大于基准值的索引
        while i <= u and arr[i] <= temp:
            i += 1
        # 从上边界开始寻找小于基准值的索引
        # 因为j肯定大于i, 所以索引值肯定在小区间中
        while arr[j] > temp:
            j -= 1
        # 如果小索引仍小于大索引, 调换二者位置
        if i >= j:
            break
        arr[i], arr[j] = arr[j], arr[i]
    # 将基准值的索引从下边界调换到索引分割点
    swap(arr, l, j)
    QuickSort_Perl(arr, l, j-1)
    QuickSort_Perl(arr, j+1, u)
    return arr

print('QuickSort_Perl([-22, -21, 0, 1, 2, 22])',
    QuickSort_Perl([-22, -21, 0, 1, 2, 22], 0, 5))
0
Song