🏃Quicksort - Explicação de DSA [Python] · kiluzx

O Quicksort é um dos algoritmos mais rápidos quando a questão é ordenação de sequências, existem outros como o mergesort, mas hoje o foco é só ele, o "Quicksort".

Entendendo a trinca do Quicksort

O QuickSort utiliza uma estratégia muito conhecida em computação para resolver problemas, que é "Dividir para Conquistar", também conhecida como DC.

Dividir para conquistar.
Júlio César

Essa abordagem consiste em dividir um problemas em partes menores, solucioná-las, e assim resolver o problema como um todo.

Não entendeu? Exemplo:

# Quero somar os elementos dessa lista
numbers = [1, 2, 3, 4]

Eu posso começar por separar a lista em duas partes [1, 2] -> soma = 3 e [3, 4] -> soma = 7, e depois somar os dois resultados, 3 + 7 = 10. Fiz isso com apenas 3 passos, qual é a diferença de fazer percorrendo a lista, dai seriam 4 passos.

OBS.: Não vou falar de complexidade espacial e temporal ainda não escrevi nenhum conteúdo sobre isso, então prefiro não abordar agora.

Como funciona o Quicksort?

Tendo um array qualquer, numbers = [10, 20, 15, 9, 1] ordene utilizando o QuickSort.

O primeiro passo é verificar o tamanho do array, um array vazio ou um array de apenas um elemento, não precisam ser ordenados, concorda?

array = [1] # está ordenado 
array = [] # não possui elementos

Já temos aqui que vamos chamar de caso-base. Como assim?

O QuickSort é um algoritmos recursivo, ou seja, ele chama a si mesmo e possui uma condição de parada(não literalmente, só para vc entender), mas refiro-me a parte do código em que a função não chama a si mesma, esse é o case-base, e o caso-recursivo é onde a função chama por si mesma.

Muitos problemas podem ser resolvidos com recursão, publicarei um post sobre isso em breve.

Agora, como ordenar um array? Vamos começar do pequeno, se você tiver um array de 3 elementos você pode facilmente ordená-lo. Mas como?

Comece escolhendo um aquilo que chamaremos de pivô daqui em diante, vai ser com base nele que vamos ordenar o array. numbers = [2, 1, 3], vamos escolher o elemento no index 0 como pivô, e vamos criar dois novos array que vão conter os valor menores e outro para os valores maiores que o pivô. E observe como facilmente ordenará o array.

numbers = [2, 1, 3]
pivot = numbers[0] # O valor no index 0
smaller = [i for i in numbers[1:] if i <= pivot]
larger = [i for i in numbers[1:] if i > pivot]

# Para obter o array ordenado, apenas some os array ao pivot.
print(smaller + [pivot] + larger)

Assim mesmo que o array 2 elementos você conseguirá ordená-lo, mas entre o smaller e o larger haverá sempre um vazio, porque haverá apenas 2 elementos no array.

Agora basta aplicar isso recursivamento, numa função e seu algoritmo de ordenação está pronto.

def quicksort(array: list) -> list:
    # Quando o array tiver apenas um elemento ou estiver vazio, eu não o preciso ordenar
    if len(array) <= 1:
        return array
    # Vamos utilizar aquela técnica que ordenar que ensinei acima
    else:
        # Primeiro escolha o pivô, eu escolhi o primeiro elemento do array
        pivot = array[0]

        # Agora vamos criar dois arrays que vão conter os valores menores e maiores que o pivô
        smallers = [i for i in array[1:] i <= pivot]
        largers = [i for i in array[1:] i > pivot]
    
    # Aqui está a trinca do quicksort, vamos fazer chamadas recursivas ao smallers e ao larger de modo que os array vão sendo divididos em partes ainda menores e facilmente ordenáveis
    return quicksort(smallers) + [pivot] + quicksort(largers)
    
print(quicksort([10, 20, 15, 9, 1]))
# Saída: [1, 9, 10, 15, 20]

Conclusão

A "trinca" do Quicksort é:

Escolher um pivô,
Dividir a lista em menores e maiores que ele,
Aplicar o algoritmo recursivamente.

Com isso, o array vai sendo quebrado até ficar fácil de ordenar, e tudo é remontado já na ordem certa.

Para quem não conseguiu entender, tente ver como funciona em VisualGo Sorting

E se ainda assim não entender, deixe suas dúvidas nos comentários.

🌟Obrigado por ler

Estou começando a escrever para a comunidade agora, aceito dicas e sugestões.
Estes são ensinamentos do livro Entendendo Algoritmos de Aditya Bhargava