Quicksort in Python
-
Schnelles Sortieren in Python mit der Methode
numpy.sort() -
Schnelles Sortieren in Python mit der Methode
Series.sort_values()der Pandas-Bibliothek - Implementierung von Quicksort in Python
In diesem Tutorial wird erklärt, wie man den Quicksort Algorithmusin Python implementiert und anwendet.
Quicksort ist ein Divide-and-Conquer-Algorithmus. Die schnelle Sortierung wählt ein Element als Drehpunkt aus dem Array aus und partitioniert dann das Array um den gewählten Drehpunkt in Unterarrays, indem sie Elemente, die kleiner als der Drehpunkt sind, in ein Array und Elemente, die größer als der Drehpunkt sind, in ein anderes Array legt. Wenn das Array doppelte Elemente enthält, können die Elemente, die gleich dem Drehpunkt sind, in das dritte Unterarray oder in eines der beiden Unterarrays gelegt werden, je nach Implementierung des Algorithmus. Das Array wird durch quick sort sortiert, indem die Subarrays durch rekursiven Aufruf sortiert werden.
Da der Quicksort-Algorithmus die Elemente durch Vergleich sortiert, gehört er zu den Vergleichssortieralgorithmen.
Schnelles Sortieren in Python mit der Methode numpy.sort()
Die Methode numpy.sort(array, axis, kind) nimmt ein Array als Eingabe und gibt die sortierte Kopie des Eingabe-Arrays als Ausgabe zurück. Der Parameter array ist das Array, das sortiert werden soll, axis ist die Richtung, entlang der das Array sortiert werden soll, und kind gibt den Algorithmus an, den die Methode zum Sortieren des Arrays verwendet.
Der folgende Beispielcode demonstriert, wie man die Methode numpy.sort() verwendet, um das Array mit Hilfe der schnellen Sortierung in Python zu sortieren.
import numpy as np
a = np.array([2, 3, 6, 5, 7, 8, 3, 1])
sorted_a = np.sort(a, kind="quick sort")
print(sorted_a)
Ausgabe:
[1 2 3 3 5 6 7 8]
Schnelles Sortieren in Python mit der Methode Series.sort_values() der Pandas-Bibliothek
Die Methode Series.sort_values(ascending, inplace, kind) der Pandas Library nimmt eine Pandas Series als Eingabe und gibt sortierte Serien zurück.
Das Argument ascending ist standardmäßig auf True gesetzt, so dass die Methode die Reihe in aufsteigender Reihenfolge sortiert. Wenn es auf False gesetzt ist, wird die Series in absteigender Reihenfolge sortiert. Wenn das Argument inplace auf True gesetzt ist, werden die Änderungen in der ursprünglichen Serie vorgenommen, ansonsten wird eine sortierte Kopie der Eingabe zurückgegeben. Das Argument kind legt fest, welcher Algorithmus zum Sortieren der Reihe verwendet wird, und die Methode verwendet standardmäßig den Algorithmus Quicksort.
Der folgende Beispielcode demonstriert, wie die Methode Series.sortvalues() verwendet werden kann, um die Serie in Python mit dem Quick-Sort-Algorithmus zu sortieren:
import pandas as pd
s = pd.Series([1, 2, 4, 2, 7, 5, 3, 2, 6, 8])
s.sort_values(inplace=True, kind="quick sort")
print(s)
Ausgabe:
0 1
1 2
3 2
7 2
6 3
2 4
5 5
8 6
4 7
9 8
dtype: int64
Implementierung von Quicksort in Python
Die dritte Methode kann sein, den Quicksort-Algorithmus selbst in Python zu implementieren.
Die folgende Code-Implementierung der schnellen Sortierung teilt das Array in 3 Unterarrays auf, ein Unterarray enthält Elemente, die kleiner als der Pivot sind, eines enthält Elemente, die größer als der Pivot sind, und das dritte Unterarray enthält Elemente, die gleich dem Pivot sind.
Bei jedem Aufruf der Methode erhalten wir die sortierte Position des Pivots, da wir die Werte, die kleiner und größer als der Pivot sind, voneinander trennen. Und durch rekursiven Aufruf erhalten wir das komplette sortierte Array.
Der folgende Beispielcode zeigt, wie der oben erläuterte Schnellsortieralgorithmus in Python implementiert werden kann:
def sort(array):
left = []
equal = []
right = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
left.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
return (
sort(left) + equal + sort(greater)
) # recursive calling of the sort() function
else: # return the array, when it contains only 1 element
return array