Verificando Um por Um
Busca Linear: Verificar Um por Um
Imagine que você tem 10 cartas viradas para baixo, numeradas de 1 a 10, embaralhadas em ordem aleatória.
Você quer encontrar a carta com o número 7.
Você vira as cartas uma por uma, da esquerda para a direita, até encontrá-la.
| Cenário | Verificações necessárias |
|---|---|
| Melhor caso | 1 verificação (sorte na primeira tentativa!) |
| Pior caso | 10 verificações (estava a última carta) |
| Média | cerca de 5 verificações |
Agora imagine 100 cartas. Média: cerca de 50 verificações.
1.000 cartas? Média: cerca de 500 verificações.
Vê o padrão? Dobre as cartas, dobre o trabalho. O trabalho cresce em linha reta.
Cientistas da computação chamam isso de busca linear: linear significa que o trabalho cresce como uma linha: constante & previsível.
A busca linear funciona em QUALQUER lista, ordenada ou não. Isso a torna simples. Mas pode ficar lenta.
Quantos Nomes?
Você tem uma lista de classe com 20 nomes escritos em ordem aleatória.
Você precisa encontrar o nome Zoe.
Você verifica os nomes um por um, de cima para baixo da lista.
Cortar a Lista pela Metade
Busca Binária: Pule para o Meio
A busca binária tem uma regra: a lista deve estar ordenada primeiro.
Se sua lista de 20 nomes vai de A a Z, você pode usar busca binária.
Como funciona: abra para o nome do meio (nome #10). Pergunte: Zoe vem antes ou depois deste nome?
Z vem perto do final do alfabeto, então Zoe vem DEPOIS do meio. Jogue fora a primeira metade. Agora você tem apenas os nomes 11-20 restantes.
Verifique o meio desses 10 nomes (nome #15). Z vem depois de M, então Zoe vem depois do nome #15. Jogue fora os nomes 11-14. Agora você tem os nomes 16-20.
Continue cortando pela metade. Cada verificação remove metade dos nomes restantes.
| Tamanho da lista | Máx. verificações com busca binária |
|---|---|
| 20 nomes | no máximo 5 verificações |
| 1.000 nomes | no máximo 10 verificações |
| 1.000.000 nomes | no máximo 20 verificações |
Compare isso com busca linear em 1.000.000 de nomes: uma média de 500.000 verificações.
A busca binária corta a lista pela metade a cada vez. Cortar pela metade repetidamente chega a 1 muito rapidamente: é por isso que permanece tão rápida.
Encontre 'fig' em uma Lista Ordenada
Aqui está uma lista ordenada de 8 palavras:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
Você quer encontrar fig usando busca binária.
Lembre-se: verifique o meio, pergunte se seu alvo vem antes ou depois, então corte a lista pela metade.
Trocando Vizinhos para Ordenar
Bubble Sort: Compara Vizinhos & Troca
O bubble sort coloca uma lista em ordem comparando dois itens vizinhos de cada vez.
Se dois vizinhos estão fora de ordem: troque-os.
Continue fazendo passagens pela lista até que nada precisar ser trocado.
Exemplo: ordenar [5, 3, 8, 1]
Passagem 1:
- Compare 5 & 3. 5 > 3, então troque → [3, 5, 8, 1]
- Compare 5 & 8. 5 < 8, sem troca → [3, 5, 8, 1]
- Compare 8 & 1. 8 > 1, então troque → [3, 5, 1, 8]
Passagem 2:
- Compare 3 & 5. OK → [3, 5, 1, 8]
- Compare 5 & 1. 5 > 1, troque → [3, 1, 5, 8]
- Compare 5 & 8. OK → [3, 1, 5, 8]
Passagem 3:
- Compare 3 & 1. 3 > 1, troque → [1, 3, 5, 8]
- Compare 3 & 5. OK. Compare 5 & 8. OK.
Pronto! [1, 3, 5, 8] ✓
Observe: o maior número borbulha até o final da lista em cada passagem. É assim que bubble sort recebe seu nome.
Bubble sort funciona. Não é o mais rápido para listas grandes, mas é fácil de entender: perfeito para aprender.
Ordene [4, 2, 7, 1] com Bubble Sort
Ordene esta lista usando bubble sort: [4, 2, 7, 1]
Mostre a lista após cada passagem. Conte quantas passagens são necessárias para terminar.