Entendendo Algoritmos - Primeira Semana
Tags: beginners, python, programming, hacktoberfest23
Published: 2023-10-06 15:08:56

> *Um algoritmo é um conjunto de instruções que realizam uma tarefa. Cada trecho de código poderia ser chamado de um algoritmo, mas este livro trata dos trechos mais interessantes.* 
Aditya Y. Bhargava


Caso você esteja chegando no rolê de paraquedas, eu sugiro que inicie por este texto: [Entendendo Algoritmos-introdução](https://dev.to/loremimpsu/entendendo-algoritmos-introducao-53f0). No texto eu te dou um breve caminho das pedras amarelas para te ajudar a chegar ao tão sonhado entendimento de algoritmos. 

## Primeiro capítulo - introdução a algoritmos

Estamos iniciando este novo livro e logo de cara já te aviso que não, este não vai ser um resumo. Este livro já resumido demais. Diferente do livro do Código limpo, este livro é uma versão simplificada de todo o assunto envolvendo algoritmos. Porém, como sou uma mulher difícil (HAHAHAHA) vou dificultar um pouco as coisas, disponibilizando para quem preferir se aprofundar mais um material mais detalhado sobre o algoritmo estudado, sua complexidade e o cálculo.

No primeiro capítulo, o Bhargava nos apresenta conceitos introdutórios como big O notation, cálculo de logarítmo, e o primeiro algoritmo do livro, a **busca binária**.  
Antes de falarmos da busca binária em si, vamos focar na busca. O ato de percorrer uma estrutura de dados procurando um valor dentre vários. O que chamamos de [busca sequencial](http://desenvolvendosoftware.com.br/algoritmos/busca/busca-sequencial.html), a busca binária nada mais é que uma busca onde tentamos diminuir a quantidade de interações que o código vai ter. 
Tá mas que interações são essas? vamos ao código:

```python
def busca_seq(lista, p):
   for i in lista:
      if(i == p):
          return i;
   return 0
```
Vamos analisar o código. Ele é um código pequeno, uma busca simples em uma lista, retornando o primeiro que encontrar que possua o valor *p*. Para um código de execução normal, ele é consideravelmente pequeno, para um código que vai receber um trilhão de entradas, este código é custoso. Imagine se o *p* for encontrado no último valor da lista? teríamos feito um trilhão de interações para encontrar apenas um valor.
A busca binária nos dá o poder de diminuir a quantidade de interações por log(n). Compare os valores de crescimento dos dos gráficos:

![pesquisa linear](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8x9yx9ewr6kr7gmqrxiu.png)

![pesquisa binária](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o4ynyj7pz9jgqer2d3je.png)

As duas pesquisas são bastante utilizadas, porém o pulo do gato é saber quando você pode utilizar uma e quando pode utilizar outra. Normalmente, esta é uma das questões de várias sobre algoritmos que você vai se deparar em um desafio técnico ou entrevista técnica. Caso você queira aprofundar o conhecimento sobre os dois algoritmos:
 - [Busca sequencial](https://algoritmosempython.com.br/cursos/algoritmos-python/pesquisa-ordenacao/pesquisa-linear/)
 - [Busca binária](https://algoritmosempython.com.br/cursos/algoritmos-python/pesquisa-ordenacao/pesquisa-binaria/)

## Segundo capítulo - Ordenação por seleção

Neste capítulo, temos a introdução de dois tipos de estruturas de dados que são um pouco generalizadas para os novos programadores. O que de fato acontece é que poucos de nós tivemos o contato com as formas de listas e arrays da maneira que o livro apresenta. 

Hoje na maioria das linguagens de programação, não existe o conceito de arrays com o tamanho fixo. O array acabou se tornando um híbrido de uma lista encadeada, ao qual sabemos o tamanho do array no momento em que o último objeto foi adicionado, adicionamos elementos de maneira que o seu tamanho se expande, e acessamos valores através do seu índice. Hoje linguagens como Javascript já possuem métodos como o [Array.from()](https://developer.mozilla.org/pt-BR/docs/Web/JavaScript/Reference/Global_Objects/Array/from) que nos entrega uma nova lista a partir de uma comparação ou na adição de um novo elemento no meio da lista. 
O que parece muito bom para as nossas vidas de reles programadores de software é um pesadelo em questões de desempenho. Nem sempre as linguagens utilizam métodos de arrays (ou listas) que proporcionam o custo-benefício para o seu produto. Algumas consultas para inserção ou deleção podem custar O(n^2) para uma operação que em uma estrutura de dados "arcaica" seria O(1) ou talvez O(n). Daí vem a necessidade de se aprender a utilizar tipos brutos de estruturas de listas encadeadas ou arrays, para melhor desempenho. 

> Um exercício muito bom para fixação do conceito de array e lista encadeada é tentar fazer uma estrutura de dado híbrida entre as duas estruturas e calcular seu possível custo computacional em big O.

Para estudar mais sobre listas encadeadas e arrays e suas problemáticas, acesse este material:
- [Listas encadeadas](https://joaoarthurbm.github.io/eda/posts/linkedlist/) 
- [Arrays](https://joaoarthurbm.github.io/eda/posts/arraylist/)

Constantemente ligado a listas encadeadas e arrays, temos outro conceito que foi pouco abordado no livro. O conceito de filas e pilhas. 
Fila é uma estrutura de dados que possui regras de inserção e processamento. O chamado FIFO, *first in first out* ou o primeiro que chega é o primeiro a sair, nos dita uma regra de inserção de dados nesta estrutura vai ser dada sempre ao final da estrutura, enquanto a sua remoção será sempre o primeiro elemento. 
 
![filas](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w1q3079rgo7qavsm6ey4.png)

Para saber mais sobre a fila, acesse [aqui](https://algoritmosempython.com.br/cursos/algoritmos-python/estruturas-dados/filas/)

Já as pilhas, vai funcionar com a regra de inserção e processamento que chamamos de LIFO, *last in first out*, diferente das filas, a pilha não vai trabalhar com localização, e sim com o conceito espacial de Topo e Base. Como uma pilha de prato, quando você adiciona um prato a pilha, sempre vai ser adicionada ao Topo. No momento de lavar, também. Sempre vai sair o primeiro da fila. 

![pilhas](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x0scnuyr4u9as5hob2lp.png)

Para saber mais da pilha, acesse [aqui](https://algoritmosempython.com.br/cursos/algoritmos-python/estruturas-dados/pilhas/)

Tá, agora vocês me perguntam o porquê de falar sobre estas estruturas? Para saber mais sobre o processamento de dados em um sistema operacional e acesso a memória.
Existe toda uma arquitetura de dados e acesso de informações que o sistema operacional utiliza, a utilização de filas e pilhas em memória é um dos assuntos que em algum momento da sua carreira vai te dar uma baita dor de cabeça (ou não, se você ficar limitado ao CRUD). Para saber mais sobre, acesse este material para [processos e threads](https://cos.ufrj.br/~vitor/aulas/COS773/slides/aulas_2.html) e este para saber mais sobre [memória virtual e alocação](https://cos.ufrj.br/~vitor/aulas/COS773/slides/aulas_8.html).

Logo após o assunto de arrays e lista encadeada, o autor nos apresenta o algoritmo de ordenação mais utilizado e conhecido por todos os desenvolvedores, o algoritmo de seleção. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wra7euqgnz5yra3kawdx.png)

Mesmo sendo o mais conhecido, o selection sort não é o mais performático. Ele faz parte do conjunto de algoritmos de ordenação da base O(n^2) e fica problemático de executar se o número de itens for muito grande, podendo ocorrer estouro de memória. 

Além do selection sort, temos dois outros algoritmos fáceis de aprender mas que o seu custo deve ser ponderado, o Bubble sort e o insertion sort. Caso queiram saber mais:

- [Bubble Sort](https://henriquebraga92.medium.com/algoritmos-de-ordena%C3%A7%C3%A3o-i-bubble-sort-c162a67261ef)

- [Insertion Sort](https://joaoarthurbm.github.io/eda/posts/insertion-sort/)

E para finalizar, a tia deixa uma dica. Sempre que possível, tente exercitar os conceitos em paralelo. Por exemplo, a ordenação sempre é necessária para que uma busca binária seja efetuada. Que tal criar um algoritmo que receba uma lista e ordene os seus itens para então fazer a busca de um item? Ou talvez você deseje adicionar a uma lista encadeada, itens de forma decrescente, onde o seu primeiro item será o maior valor. Você pode ordenar um array e utilizar métodos de pilha para remover e adicionar a uma lista encadeada como uma fila. 
São exercícios assim que fixarão o conteúdo do livro a sua cachola. Além de tornar bem mais legal a implementação, fugindo do copy and paste infinito. 

Bom, se vemos na próxima semana, onde irei problematizar mais uma parte deste livro "facinho". Se possível, reaja ao post, compartilhe e me deixe um comentário, falando sobre o que achou!


![terapia](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r8dmqqw3ik7lufpy4msd.jpg)