Algoritmos e estrutura de dados

Um algoritmo é uma receita, ou seja, uma sequência finita de passos lógicos e bem definidos, criada para resolver um problema específico ou executar uma tarefa.

• Análise (Eficiência): A "qualidade" de um algoritmo é medida por sua complexidade:

Complexidade de Tempo: Quão rápido o algoritmo executa (quantos passos ele leva) à medida que a quantidade de dados aumenta.

Complexidade de Espaço: Quanta memória o algoritmo consome para rodar.

Estruturas de dados são formas sistemáticas de organizar, armazenar e gerenciar dados no computador, para que possam ser acessados e modificados de forma eficiente. Alguns exemplos:

Tipos Principais (Lineares):

• Array (Vetor/Lista): Uma coleção de itens armazenados em locais de memória contíguos. Ótimo para acesso rápido pelo índice (ex: lista[5]).

• Lista Ligada (Linked List): Uma coleção de itens onde cada um "aponta" para o próximo. Ótimo para inserir e remover itens no meio da lista.

• Pilha (Stack): Segue a regra "Último a Entrar, Primeiro a Sair" (LIFO - Last In, First Out). Pense em uma pilha de pratos.

• Fila (Queue): Segue a regra "Primeiro a Entrar, Primeiro a Sair" (FIFO - First In, First Out). Pense em uma fila de banco.

Tipos Principais (Não-Lineares):

• Árvores (Trees): Estrutura hierárquica. Ótima para buscas rápidas (ex: Árvore Binária de Busca) ou para representar hierarquias (ex: pastas de arquivos).

• Grafos (Graphs): Estrutura que representa conexões (redes). Usado para mapas (GPS), redes sociais, etc.

- Dica:

• Fazer uma busca binária em uma lista ligada é ineficiente

Algoritmos de Busca

Os Algoritmos de Busca são métodos usados para verificar se uma dada informação (x) ocorre em uma sequência (seq). O objetivo é implementar a lógica por trás de operações comuns em Python, como o operador in (x in seq) ou o método .index().

Existem duas estratégias principais: a busca sequencial e a busca binária.

Busca Sequencial

• Definição: Também conhecida como busca linear, é o método de busca mais simples.
• Estratégia: Percorre a lista elemento por elemento, do índice 0 até o final (len(seq) - 1), comparando cada item seq[i] com x.
• Desvantagem: É ineficiente para listas grandes. No pior caso (quando x não está na lista), o algoritmo precisa varrer toda a sequência.

Código Exemplo (Busca Sequencial)

<syntaxhighlight lang="python"> def busca_sequencial(x, seq):

   (float, list) -> bool
   Retorna True se x ocorre na lista, ou False caso contrário.
   
   for i in range(len(seq)):
       if seq[i] == x:
           return True
   return False

</syntaxhighlight>

Busca Binária

• Definição: Um algoritmo de busca muito mais eficiente, que "corta" o problema pela metade a cada passo.
• Pré-requisito: A sequência OBRIGATORIAMENTE precisa estar ordenada (ex: do menor para o maior).
• Estratégia (Método do Dicionário):

1. Considere o elemento M no meio da lista.
2. Se x == M, o elemento foi encontrado.
3. Se x < M, o elemento (se existir) só pode estar na primeira metade. A segunda metade é descartada.
4. Se x > M, o elemento (se existir) só pode estar na segunda metade. A primeira metade é descartada.
5. O processo é repetido na metade restante, cortando a área de busca repetidamente.

• Vantagem (Eficiência): É extremamente rápido. Em uma lista com 1024 elementos, a busca sequencial faria 1024 testes no pior caso. A busca binária faria no máximo 10 testes (pois log₂(1024) = 10).

Código Exemplo (Busca Binária)

<syntaxhighlight lang="python"> def busca_binaria(x, seq):

    (float, list) -> int ou None
       Retorna a posição (índice) em que x ocorre na lista ORDENADA,
       ou None caso contrário.
   
   inicio = 0
   fim = len(seq) - 1
   
   while inicio <= fim:
       meio = (inicio + fim) // 2 # Divisão inteira para achar o índice do meio
       
       if seq[meio] == x:
           return meio # ACHOU! Retorna a posição.
       elif seq[meio] > x:
           # x é menor, joga fora a metade da direita
           fim = meio - 1
       else: # seq[meio] < x
           # x é maior, joga fora a metade da esquerda
           inicio = meio + 1
           
   return None # O loop terminou (inicio > fim) e não achou.

</syntaxhighlight>

Algoritmos de Ordenação

Um Algoritmo de Ordenação (ou Sorting Algorithm) é um algoritmo que tem como objetivo principal reorganizar os elementos de uma sequência (como uma lista) em uma ordem específica, geralmente numérica (crescente ou decrescente) ou alfabética.

A ordenação é uma das tarefas mais fundamentais da computação, pois muitas outras tarefas se tornam triviais ou muito mais eficientes se os dados já estiverem ordenados. Um exemplo clássico é a Busca Binária, que exige que a sequência esteja ordenada para funcionar.

Embora o Python já forneça métodos de ordenação altamente eficientes (como o método seq.sort() e a função sorted(seq)), o objetivo aqui é entender as diferentes estratégias e "receitas" lógicas usadas para construir esses algoritmos.

Seleção Direta (Selection Sort)

• Definição: Um dos algoritmos de ordenação mais simples e intuitivos.
• Estratégia:

1. 1. Encontre o menor elemento na parte não ordenada da lista.
2. 2. Troque esse menor elemento com o primeiro elemento da parte não ordenada.
3. 3. Marque essa posição como "ordenada".
4. 4. Repita os passos 1-3 para o restante da lista, até que toda a lista esteja ordenada.

Código Exemplo (Seleção Direta)

<syntaxhighlight lang="python">

def selection_sort(seq):

   (list) -> None
   Ordena a lista 'seq' em ordem crescente, usando Seleção Direta.
   Atenção: esta função MODIFICA a lista original.
   
   n = len(seq)
   
   # Loop 'i' percorre as posições que devem receber o menor valor
   # (vai de 0 até n-2)
   for i in range(n):
       # 1. Encontre o índice do menor elemento
       idx_min = i # Assume que o menor é o primeiro (i)
       
       # Loop 'j' procura por um menor ainda
       for j in range(i + 1, n):
           if seq[j] < seq[idx_min]:
               idx_min = j # Achamos um novo menor!
       
       # 2. Troque o menor (idx_min) com a posição atual (i)
       #    (Isso coloca o i-ésimo menor elemento no lugar certo)
       seq[i], seq[idx_min] = seq[idx_min], seq[i]
       
   # A função não precisa de 'return' pois modifica 'seq' diretamente.

1. --- Teste ---

lista_teste = [64, 25, 12, 22, 11] selection_sort(lista_teste) print(lista_teste) # Saída: [11, 12, 22, 25, 64] </syntaxhighlight>

Bolha (Bubble Sort)

• Definição: Um algoritmo simples que repetidamente "flutua" (ou "borbulha") o maior elemento da seção não ordenada para o seu local correto no final da lista.
• Estratégia:

1. 1. Compare o primeiro elemento com o segundo. Se estiverem fora de ordem, troque-os.
2. 2. Compare o segundo com o terceiro. Se estiverem fora de ordem, troque-os.
3. 3. Continue esse processo até o final da lista. (Após esta primeira "passada", o maior elemento estará garantidamente na última posição).
4. 4. Repita o processo (passadas 1-3) para a lista, mas agora parando na penúltima posição (pois a última já está correta).
5. 5. Continue repetindo as passadas, diminuindo o limite a cada vez, até que a lista esteja ordenada.
6. 6. (Otimização): Se uma "passada" inteira for feita e nenhuma troca ocorrer, a lista já está ordenada e o algoritmo pode parar.

Código Exemplo (Bolha)

<syntaxhighlight lang="python"> def bubble_sort(seq):

   (list) -> None
   Ordena a lista 'seq' em ordem crescente, usando o método Bolha.
   
   n = len(seq)
   
   # Loop 'while' controla as "passadas" pela lista
   # Continua rodando enquanto houver trocas (trocou == True)
   trocou = True
   while trocou:
       trocou = False # Assume que não haverá trocas nesta passada
       
       # Loop 'i' faz as comparações par-a-par
       # O 'n-1' no range é porque a cada passada,
       # o último item já está ordenado, então diminuímos o limite.
       for i in range(n - 1):
           if seq[i] > seq[i+1]:
               # 1. Se estão fora de ordem, troque!
               seq[i], seq[i+1] = seq[i+1], seq[i]
               # 2. Avisa que uma troca ocorreu
               trocou = True 
               
       # Otimização: diminui o tamanho da próxima passada
       n = n - 1 

1. --- Teste ---

lista_teste = [5, 1, 4, 2, 8] bubble_sort(lista_teste) print(lista_teste) # Saída: [1, 2, 4, 5, 8] </syntaxhighlight>

Inserção Direta (Insertion Sort)

• Definição: Um algoritmo que constrói a lista ordenada final, um elemento de cada vez. É como um jogador de cartas organiza sua mão.
• Estratégia:

1. 1. Comece com a "parte ordenada" sendo apenas o primeiro elemento (índice 0).
2. 2. Pegue o próximo elemento não ordenado (a "chave").
3. 3. Compare a "chave" com os elementos na "parte ordenada" (indo da direita para a esquerda).
4. 4. "Empurre" todos os elementos maiores que a "chave" uma posição para a direita, para abrir espaço.
5. 5. Insira a "chave" no espaço que abriu.
6. 6. Repita os passos 2-5 até que todos os elementos tenham sido inseridos na parte ordenada.

Código Exemplo (Inserção Direta)

<syntaxhighlight lang="python"> def insertion_sort(seq):

   (list) -> None
   Ordena a lista 'seq' em ordem crescente, usando Inserção Direta.
   
   
   # Loop 'i' começa no SEGUNDO elemento (índice 1)
   # (Consideramos o primeiro item como a 'parte ordenada' inicial)
   for i in range(1, len(seq)):
       
       # 1. Pega o próximo item (a "chave")
       chave = seq[i]
       
       # 2. Pega o índice do último item da 'parte ordenada'
       j = i - 1 
       
       # 3. Loop 'while' para "empurrar" os maiores
       #    Enquanto 'j' não saiu do início E a 'chave' for menor...
       while j >= 0 and chave < seq[j]:
           seq[j + 1] = seq[j] # ...empurra o elemento maior para a direita
           j = j - 1           # ...anda 'j' para a esquerda
           
       # 4. Insere a 'chave' no espaço aberto
       seq[j + 1] = chave

1. --- Teste ---

lista_teste = [12, 11, 13, 5, 6] insertion_sort(lista_teste) print(lista_teste) # Saída: [5, 6, 11, 12, 13] </syntaxhighlight>