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)
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
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)
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
wählen Sie das erste Element von Array _
arr[0]_ als Pivot aus_
[arr[0]]_qsortdie Elemente des Arrays, die kleiner sind als Pivot mitList Comprehensionqsort([x for x in arr[1:] if x < arr[0]])qsortdie Elemente des Arrays, die größer sind als Pivot mit _List Comprehension_qsort([x for x in arr[1:] if x >= arr[0]])
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
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]])
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:
- Wählen Sie einen Pivot-Datenpunkt aus.
- 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.
- 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.
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)
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]])
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)
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
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: -
- alle Elemente zwischen Pivot und i sind kleiner als der Pivot und
- 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.
Der Algorithmus besteht aus 4 einfachen Schritten:
- 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
- Fügen Sie dem jeweiligen Teil Elemente hinzu, indem Sie sie mit dem Schwenkelement vergleichen. (Erklärung in Kommentaren)
- Rekursieren Sie diesen Algorithmus, bis alle Elemente im Array sortiert wurden
- 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.
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])
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)
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)
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])
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 ?
- Grundsätzlich wählen wir das erste Element als Drehpunkt aus unserer Liste aus und erstellen dann zwei Unterlisten.
- Unsere erste Unterliste enthält die Elemente, die weniger als Pivot sind
- Unsere zweite Unterliste enthält unsere Artikel, die größer oder gleich dem Pivot sind
- 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
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))
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)
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 []
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)
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()
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]))
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]
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))
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
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()
- Zuerst deklarieren wir den ersten Wert im Array als Pivot_value und setzen außerdem die linken und rechten Markierungen
- 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
- dann wenden wir den Partitionsprozess an
- 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
- 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
# 编程珠玑实现
# 双向排序: 提高非随机输入的性能
# 不需要额外的空间,在待排序数组本身内部进行排序
# 基准值通过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))