Como algoritmos melhoram a performance do seu código
Tags: algorithms, beginners, computerscience
Published: 2023-03-26 19:39:51

Algoritmos são conjuntos de instruções que direcionam um computador para realizar uma tarefa específica. Eles estão presentes em todas as áreas da programação e são essenciais para otimizar o desempenho do código. O objetivo desse artigo é introduzir a importância dos algoritmos usando como exemplo a performance na ordenações de listas. 

Imagine o seguinte cenário: temos uma lista de 10 números `[3, 7, 2, 8, 1, 6, 9, 4, 5, 0]` e queremos que seja ordenada do menor para o maior.

Nesse caso, dois algoritmos bastante conhecidos (não são os únicos e nem os melhores, mas servem como exemplo) na área de ordenação de listas são o **bubble sort** e o **quick sort**. 

O _bubble sort_ funciona da seguinte maneira: ele percorre a lista diversas vezes, comparando cada elemento com o seu sucessor e trocando o lugar de ambos caso necessário. Esse processo é repetido até que a lista esteja completamente ordenada. O tempo de execução médio desse algoritmo é `O(n^2)`. 

Nota: `O()` é uma notação de medida de complexidade de tempo chamada [**Big O**](https://www.freecodecamp.org/portuguese/news/o-que-e-a-notacao-big-o-complexidade-de-tempo-e-de-espaco/). Em resumo, serve pra descrever quantas ações aquele algoritmo precisa performar pra que atinja seu objetivo

Imaginando nosso caso hipotético de uma lista com 10 números, cada número precisaria percorrer toda a lista e comparar os valores, o que são 10 ações pra cada elemento, por isso a complexidade de tempo é **n^2**, que no caso seria **10^2 = 10*10**, que é igual a **100**. **Ou seja, o _bubble sort_ requere 100 ações pra ordenar uma lista de 10 números**. Extrapolando o exemplo pra uma lista de 100 números, a quantidade de ações requeridas sobe pra **10.000** (ou **100^2 = 100*100**)!

Por outro lado, o _quick sort_ é um algoritmo que utiliza uma estratégia conhecida como "_dividir para conquistar_". Ele escolhe um elemento da lista como **pivô** e, em seguida, divide a lista em duas partes: uma contendo elementos **menores que o pivô** e outra contendo elementos **maiores que o pivô**. Esse processo é repetido até que toda a lista esteja ordenada.  

Voltando ao nosso caso de uma lista com 10 números, o _quick sort_ escolheria um elemento do array para ser o pivô. Neste caso, vamos escolher o elemento do meio, que é o número 1.

O array é dividido em duas partes: **uma parte com valores menores** que o pivô e outra **com valores maiores ou iguais** ao pivô.
A parte dos menores valores fica à esquerda do pivô, e a parte dos maiores valores fica à direita do pivô. Os valores iguais ao pivô podem ficar em qualquer uma das partes.

A lista então é dividida em `[3, 2, 1, 4, 0]` e `[7, 8, 6, 9, 5]`.

Agora devemos **repetir** o processo pra ambas as listas.

Vamos escolher um novo pivô para cada parte, e dividir o array novamente em duas partes: uma com valores menores que o pivô e outra com valores maiores ou iguais ao pivô.

Para a lista da esquerda, escolhemos o elemento 2 como pivô e dividimos em `[1, 0]` e `[3, 2, 4]`. Para a lista da direita, escolhemos o elemento 8 como pivô e dividimos em `[7, 6, 5]` e `[9]`.

Agora repetimos o processo até que todas as partes do array tenham tamanho 1 ou 0. Quando uma parte do array tem tamanho 1 ou 0, significa que ela já está ordenada.

Ao final, o resultado será nossa lista ordenada da seguinte forma: `[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]`.


O tempo de execução médio do _quick sort_, portanto, é `O(n * log2(n))`, que significa, nesse caso, **10 * log2(10) = 10 * 3,321 = 33,2**. Extrapolando o exemplo pra uma lista de 100 números temos **100 * log2(100) = 100 * 6,643 = 664,3**. Ou seja, o algoritmo de _quick sort_ precisa performar, em média, **664,3** ações pra ordenar uma lista de 100 números, bem menor do que o tempo de execução do _bubble sort_, que precisa de **10.000 ações**!

Apenas com o uso de algoritmos e matemática diminuímos em quase **1.400%** o tempo de execução do nosso código, por isso o domínio do assunto é tão crucial para programadores.

Em resumo, os algoritmos são ferramentas importantes para a otimização do desempenho do código. Conhecer os fundamentos da programação é essencial para auxiliar na resolução de problemas de forma correta e **eficiente**.

Dica de leitura: _Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos_, **Aditya Y. Bhargava**.