Classificação rápida em Python

  1. Classificação rápida em Python usando o método numpy.sort()
  2. Classificação rápida em Python usando o método Series.sort_values() da biblioteca Pandas
  3. 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 eixo é 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 ascendente é Verdadeiro, portanto o método classifica a série em ordem crescente. Se for definido como Falso, as Séries 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