Classificação rápida em Python
-
Classificação rápida em Python usando o método
numpy.sort() -
Classificação rápida em Python usando o método
Series.sort_values()da biblioteca Pandas - Implementação de classificação rápida em Python
Este tutorial explicará como implementar e aplicar o algoritmo de classificação rápida em Python.
A classificação rápida é um algoritmo de divisão e conquista. A classificação rápida escolhe um elemento como um pivô do array e, em seguida, particiona a matriz em torno do pivô selecionado em subarrays, colocando elementos menores que o pivô em un array e elementos maiores que o pivô em outra matriz. Se a matriz contém elementos duplicados, os elementos iguais ao pivô podem ser colocados na terceira submatriz ou em qualquer uma das duas subarrays, dependendo da implementação do algoritmo. O array é classificado por classificação rápida, classificando os subarrays por meio de chamadas recursivas.
Como o algoritmo de classificação rápida classifica os elementos comparando-os, ele pertence ao algoritmo de classificação por comparação.
Classificação rápida em Python usando o método numpy.sort()
O método numpy.sort(array, axis, kind) recebe um array como entrada e retorna a cópia ordenada do array de entrada como saída. O parâmetro array é o array que queremos ordenar, o axis é ao longo do qual queremos ordenar o array e o kind especifica o algoritmo que o método irá usar para ordenar o array, o seu valor predefinido é rápido organizar.
O código de exemplo a seguir demonstra como usar o método numpy.sort() para classificar a matriz usando a classificação rápida em 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)
Resultado:
[1 2 3 3 5 6 7 8]
Classificação rápida em Python usando o método Series.sort_values() da biblioteca Pandas
O método Series.sort_values(ascending, inplace, kind) da biblioteca Pandas pega uma Pandas Series como entrada e retorna séries ordenadas.
O valor padrão do argumento ascending é True, portanto o método classifica a série em ordem crescente. Se for definido como False, as Series serão classificadas em ordem decrescente. Se o argumento inplace for definido como True, as alterações serão feitas na série original; caso contrário, uma cópia classificada da entrada será retornada. O argumento kind determina qual método de algoritmo usará para classificar a série, e o método usa o algoritmo de classificação rápida por padrão.
O código de exemplo a seguir demonstra como Series.sortvalues() pode ser usado para classificar a série em Python usando o algoritmo de classificação rápida:
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)
Resultado:
0 1
1 2
3 2
7 2
6 3
2 4
5 5
8 6
4 7
9 8
dtype: int64
Implementação de classificação rápida em Python
O terceiro método pode ser implementar o algoritmo de classificação rápida por conta própria em Python.
A implementação de código a seguir da classificação rápida divide a matriz em 3 subarrays, uma submatriz contém elementos que são menores que o pivô, um contém elementos maiores que os pivôs e a terceira submatriz contém elementos iguais ao pivô.
Em cada chamada do método, obteremos a posição classificada do pivô, pois estamos separando os valores menores e maiores do que o pivô. E por chamada recursiva obteremos o array ordenado completo.
O código de exemplo abaixo demonstra como implementar o algoritmo de classificação rápida explicado acima em 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