Algoritmos de Busca e Ordenação

O que é um Algoritmo?

Um algoritmo é uma sequência finita e inequívoca de instruções passo-a-passo projetada para resolver um determinado problema computacional.

---

⚡ Simulador Visual de Algoritmos (Busca e Ordenação)

Experimente em tempo real como a CPU manipula células na memória RAM para ordenar ou localizar valores:

📊

Simulador Visual de Algoritmos (Busca e Ordenação)

Veja o fluxo de comparações, trocas e notação Big-O $O(n)$ na Memória RAM

Bubble Sort — Ordenação por Bolha O(n²)Merge Sort — Divisão e Conquista O(n log n)Busca Linear — Procura Sequencial O(n)Busca Binária — Divisão ao Meio O(log n)

Velocidade:

45

12

89

34

67

23

90

15

Comparações Efetuadas

0

Trocas de Memória (Swaps)

0

Complexidade de Tempo (Big-O)

O(n²)

💡 Como Funciona: O Bubble Sort compara elementos adjacentes na memória RAM e troca de posição (swap) se o primeiro for maior que o segundo — repare como as barras deslizam fisicamente ao trocar de lugar.

---

Complexidade de Tempo e Notação Big-O

A Notação Big-O ($O$) descreve como o tempo de execução de um algoritmo cresce à medida que o tamanho dos dados de entrada ($n$) aumenta.

Algoritmo	Melhor Caso	Caso Médio	Pior Caso	Espaço Auxiliar
Busca Linear	$O(1)$	$O(n)$	$O(n)$	$O(1)$
Busca Binária	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$
Bubble Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$

---

1. Busca Linear vs Busca Binária

Busca Linear ($O(n)$)

Percorre a lista elemento por elemento a partir do início. Funciona em listas não ordenadas, mas torna-se lenta para grandes volumes de dados.

Busca Binária ($O(\log n)$)

Exige que a lista esteja previamente ordenada. O algoritmo divide a lista ao meio repetidamente:

1. Compara o elemento do meio com o valor procurado.
2. Se for menor, descarta a metade esquerda. Se for maior, descarta a direita.

Para encontrar um item entre 1.000.000 de elementos:
- Busca Linear: até 1.000.000 de comparações.
- Busca Binária: no máximo 20 comparações! (2²⁰ ≈ 1.000.000)

---

2. Algoritmos de Ordenação

Bubble Sort ($O(n^2)$)

Compara elementos adjacentes e os troca de lugar (swap) se estiverem na ordem errada. Os maiores valores "flutuam" para o final da lista a cada passada.

Merge Sort ($O(n \log n)$)

Utiliza a estratégia de Divisão e Conquista:

1. Divide a lista recursivamente em sub-listas de 1 elemento.
2. Intercala (merge) as sub-listas de forma ordenada.