Como Implementar o Algoritmo de Ordenação Quicksort em Python

O Quicksort é um dos algoritmos de ordenação mais utilizados na ciência da computação. Ele é rápido, eficiente e amplamente adotado em diversas aplicações. Nesta seção, vamos explorar como implementar o algoritmo de ordenação Quicksort em Python, passo a passo.

Antes de começarmos a implementação, é importante destacar que o Quicksort utiliza o conceito de dividir e conquistar para ordenar os elementos de um array. Ele parte do princípio de que um array vazio ou com apenas um elemento já está ordenado.

O primeiro passo é escolher um elemento do array como “pivot”. O pivot será utilizado como referência para dividir o array em duas partes: uma com elementos menores que o pivot e outra com elementos maiores. Em seguida, são criados subarrays, que são ordenados de forma recursiva usando o Quicksort.

Sem mais delongas, vamos ao passo a passo para implementar o algoritmo de ordenação Quicksort em Python:

1. Escolha o último elemento do array como pivot.
2. Inicie um índice chamado “i” no valor -1.
3. Percorra o array do primeiro ao penúltimo elemento.
   • Se o elemento atual do array for menor ou igual ao pivot:
   1. Incremente o valor do índice “i”.
   2. Troque os elementos nas posições “i” e “j”, onde “j” é o índice atual da iteração.
4. Realize uma troca final do elemento seguinte ao último utilizado como pivot com o elemento na posição “i+1”.
5. Divida o array em duas partes a partir da posição “i+1”.
6. Execute o Quicksort recursivamente nos subarrays esquerdo e direito.

Uma abordagem em Python para implementar o Quicksort seria assim:

def quicksort(array):
    if len(array) <= 1:
        return array
    
    pivot = array[-1]
    i = -1
    
    for j in range(len(array)-1):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]
    
    array[i+1], array[-1] = array[-1], array[i+1]
    
    left = quicksort(array[:i+1])
    right = quicksort(array[i+2:])
    
    return left + [array[i+1]] + right

Entendendo o Funcionamento do Quicksort

Para entender melhor como o algoritmo de ordenação Quicksort funciona, vamos explorar um exemplo passo a passo. Considere o seguinte array:

[5, 2, 9, 1, 7, 6, 4]

Passo 1: Escolha um elemento como pivot, neste caso, escolheremos o último elemento, que é o 4.

Passo 2: Percorra o array e divida-o em duas partes: uma com elementos menores ou iguais a 4 e outra com elementos maiores. O array ficará assim:

[2, 1, 4, 5, 7, 6, 9]

Passo 3: Repita o processo para os subarrays esquerdo e direito. Para o subarray esquerdo, o pivot será o 1:

[1, 2]

Para o subarray direito, o pivot será o 9:

[5, 7, 6, 9]

Passo 4: Recursivamente, divida novamente os subarrays em subarrays menores até que todos estejam ordenados.

Dessa forma, o Quicksort é capaz de ordenar eficientemente o array inicial. Ele garante que todos os elementos menores estejam à esquerda do pivot e que todos os elementos maiores estejam à direita.

O Quicksort é um algoritmo de ordenação amplamente utilizado devido à sua eficiência e rapidez. Sua implementação em Python é relativamente simples, desde que se entenda bem o conceito e o funcionamento por trás dele. Agora que você sabe como implementar o Quicksort, você pode utilizá-lo para ordenar arrays em seus projetos Python.

A Awari é a melhor plataforma para aprender sobre programação no Brasil.

Aqui você encontra cursos com aulas ao vivo, mentorias individuais com os melhores profissionais do mercado e suporte de carreira personalizado para dar seu próximo passo profissional e aprender habilidades como Data Science, Data Analytics, Machine Learning e mais.

Já pensou em aprender de maneira individualizada com profissionais que atuam em empresas como Nubank, Amazon e Google? Clique aqui para se inscrever na Awari e começar a construir agora mesmo o próximo capítulo da sua carreira em dados.