Ordenar e buscar em listas
- 1. Aprenda
- 2. Confira
- 3. Pratique
A ideia principalExistem receitas clássicas para ordenar uma lista e para encontrar um item nela. Algumas são muito mais rápidas que outras.
Para ordenar, um jeito simples é a ordenação por seleção: achar o menor, colocar no começo, e repetir com o resto. Outro é a bolha: comparar vizinhos e trocar quando estão fora de ordem.
Para buscar, você pode olhar item por item (busca sequencial). Se a lista já estiver ordenada, use a busca binária: olhe o meio, descarte a metade em que o item não pode estar e repita. Em 1000 itens, ela acha em no máximo 10 tentativas.
- [2, 5, 8, 12, 16, 23, 38] Procurando 23
- Meio = 12. 23 é maior: fica a metade da direita
- [16, 23, 38] Meio = 23
- Achou em 2 tentativas!
No dia a dia: Procurar uma palavra no dicionário: você abre no meio e decide se vai para a frente ou para trás, sem ler página por página.
Palavras para lembrar
- Ordenação
- colocar os itens em ordem (crescente, alfabética).
- Busca binária
- busca que divide uma lista ordenada ao meio a cada passo.
Confira se entendeu
Agora pratique
Use o que você acabou de ler. Cada atividade conta no seu progresso: com 80% ou mais você fica proficiente em EF08CO03.
Outros assuntos do 8º ano
Habilidade EF08CO03 da BNCC: Utilizar algoritmos clássicos de manipulação sobre listas. Professor(a): planos, slides e fichas na página da habilidade.