Tri rapide en Python
-
Tri rapide en Python avec la méthode
numpy.sort() -
Tri rapide en Python en utilisant la méthode
Series.sort_values()de la bibliothèque Pandas - Implémentation de l’algorithme de tri rapide en Python
Ce tutoriel explique comment mettre en œuvre et appliquer l’algorithme de tri rapideen Python.
Le tri rapide est un algorithme de division et de conquête. Le tri rapide sélectionne un élément comme pivot dans le tableau et ensuite divise le tableau autour du pivot sélectionné en sous-tableaux en mettant les éléments plus petits que le pivot dans un tableau et les éléments plus grands que le pivot dans un autre tableau. Si le tableau contient des éléments en double, alors les éléments égaux au pivot peuvent être placés dans le troisième sous-tableau ou dans l’un des deux sous-tableaux selon l’implémentation de l’algorithme. Le tableau est trié par tri rapide en triant les sous-tableaux par appel récursif.
Comme l’algorithme de tri rapide trie les éléments en les comparant, il appartient à l’algorithme de tri par comparaison.
Tri rapide en Python avec la méthode numpy.sort()
La méthode numpy.sort(array, axis, kind) prend un tableau en entrée et retourne la copie triée du tableau en entrée en sortie. Le paramètre array est le tableau que nous voulons trier, le axis est le long duquel nous voulons trier le tableau, et le kind spécifie l’algorithme que la méthode utilisera pour trier le tableau, sa valeur par défaut est rapide Trier.
L’exemple de code ci-dessous montre comment utiliser la méthode numpy.sort() pour trier le tableau en utilisant le tri rapide en Python.
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)
Production :
[1 2 3 3 5 6 7 8]
Tri rapide en Python en utilisant la méthode Series.sort_values() de la bibliothèque Pandas
La méthode Series.sort_values(ascending, inplace, kind) de la bibliothèque Pandas prend une Series de Pandas comme entrée et retourne des séries triées.
La valeur par défaut de l’argument ascending est True, donc la méthode trie les séries par ordre croissant. Si elle est définie comme False, les Series seront triées par ordre décroissant. Si l’argument inplace est défini comme True, les changements seront faits dans la série originale ; sinon, une copie triée de l’entrée sera retournée. L’argument kind détermine la méthode d’algorithme qui sera utilisée pour trier les séries, et la méthode utilise par défaut l’algorithme de tri rapide.
L’exemple de code ci-dessous montre comment la fonction Series.sortvalues() peut être utilisée pour trier les séries en Python en utilisant l’algorithme de tri rapide :
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)
Production :
0 1
1 2
3 2
7 2
6 3
2 4
5 5
8 6
4 7
9 8
dtype: int64
Implémentation de l’algorithme de tri rapide en Python
La troisième méthode peut être d’implémenter l’algorithme de tri rapide par nous-mêmes en Python.
L’implémentation suivante du code de tri rapide divise le tableau en 3 sous-tableaux, un sous-tableau contient des éléments inférieurs au pivot, un autre contient des éléments supérieurs aux pivots, et le troisième sous-tableau contient des éléments égaux au pivot.
À chaque appel de la méthode, nous obtiendrons la position triée du pivot, car nous séparons les valeurs inférieures et supérieures au pivot. Et par appel récursif, nous obtiendrons le tableau trié complet.
L’exemple de code ci-dessous montre comment implémenter l’algorithme de tri rapide expliqué ci-dessus en Python :
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