Ordenamiento rápido en Python
-
ordenamiento rápido en Python usando el método
numpy.sort() -
ordenamiento rápido en Python usando el método
Series.sort_values()de la biblioteca Pandas - Implementación de ordenamiento rápido en Python
Este tutorial explicará cómo implementar y aplicar el ordenamiento rápido en Python.
La ordenamiento rápido es un algoritmo de divide y vencerás. La ordenamiento rápido elige un elemento como pivote del array y luego dividel array alrededor del pivote seleccionado en submatrices colocando elementos más pequeños que el pivote en un array y elementos mayores que el pivote en otra matriz. Si el array contiene elementos duplicados, entonces los elementos iguales al pivote se pueden colocar en la tercera submatriz o en cualquiera de las dos submatrices, dependiendo de la implementación del algoritmo. El array se ordena mediante ordenamiento rápido clasificando las submatrices mediante llamadas recursivas.
Como el algoritmo de ordenamiento rápido ordena los elementos comparándolos, pertenece al algoritmo de clasificación de comparación.
ordenamiento rápido en Python usando el método numpy.sort()
El método numpy.sort(array, axis, kind) toma un array como entrada y devuelve la copia ordenada del array de entrada como salida. El parámetro array es el array que queremos ordenar, el axis es el que queremos ordenar el array, y el kind especifica el algoritmo que usará el método para ordenar el array, su valor predeterminado es ordenamiento rápido.
El siguiente código de ejemplo demuestra cómo usar el método numpy.sort() para ordenar el array usando la ordenamiento rápido 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)
Producción :
[1 2 3 3 5 6 7 8]
ordenamiento rápido en Python usando el método Series.sort_values() de la biblioteca Pandas
El método Series.sort_values(ascending, inplace, kind) de la biblioteca de Pandas toma una Series de Pandas como entrada y devuelve series ordenadas.
El valor predeterminado del argumento ascending es True, por lo que el método ordena la serie en orden ascendente. Si está configurado como False, la Series se ordenará en orden descendente. Si el argumento inplace se establece como True, los cambios se realizarán en la serie original; de lo contrario, se devolverá una copia ordenada de la entrada. El argumento kind determina qué método de algoritmo utilizará para ordenar la serie, y el método utiliza el algoritmo de ordenamiento rápido por defecto.
El siguiente código de ejemplo demuestra cómo se puede usar Series.sortvalues() para ordenar la serie en Python usando el algoritmo de ordenamiento rápido:
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)
Producción :
0 1
1 2
3 2
7 2
6 3
2 4
5 5
8 6
4 7
9 8
dtype: int64
Implementación de ordenamiento rápido en Python
El tercer método puede ser implementar el algoritmo de ordenamiento rápido por nuestra cuenta en Python.
La siguiente implementación de código de la ordenamiento rápido dividel array en 3 subarrays, un subarray contiene elementos que son menores que el pivote, uno contiene elementos mayores que los pivotes y el tercer subarray contiene elementos iguales al pivote.
En cada llamada al método, obtendremos la posición ordenada del pivote, ya que separamos los valores menores y mayores que el pivote. Y mediante una llamada recursiva obtendrá el array ordenada completa.
El código de ejemplo a continuación demuestra cómo implementar el algoritmo de ordenamiento rápido explicado anteriormente 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