🚀 Capítulo 17: Algoritmos de Ordenação Simples (Tema: Sonic)
NOTE
Este capítulo utiliza a temática de Sonic para explicar os algoritmos de ordenação simples. O Sonic precisa coletar as Esmeraldas do Caos e organizá-las por tamanho para liberar seu super poder!
1. 🎯 Objetivo da Aula
Compreender o funcionamento dos algoritmos de ordenação simples: Bubble Sort (Ordenação por Bolha) e Selection Sort (Ordenação por Seleção), identificando sua complexidade de tempo .
2. 🏢 O Cenário Prático (Seu Desafio)
O Sonic coletou 5 Esmeraldas do Caos, mas elas estão todas bagunçadas na tela. Para ativar o Super Sonic, elas precisam estar organizadas da menor para a maior.
Temos os tamanhos: [5, 2, 9, 1, 5]
O Sonic pode usar duas técnicas de corrida para ordenar:
- Técnica 1 (Bubble Sort): Ele corre comparando as esmeraldas de duas em duas. Se a da esquerda for maior que a da direita, ele as inverte. Ele faz isso até a maior esmeralda “flutuar” como uma bolha para o final da fila.
- Técnica 2 (Selection Sort): Ele corre a fileira toda procurando a menor esmeralda de todas. Quando acha (a número 1), ele a coloca na primeira posição. Depois ele procura a menor das que sobraram…
Seu desafio é entender o passo a passo dessas duas técnicas!
3. 🧠 Fundamentos: A Teoria Traduzida
Ordenar dados é uma das tarefas mais comuns e caras na computação. Os métodos simples são fáceis de entender, mas lentos para muitos dados.
🫧 1. Bubble Sort (Bolha)
Ele percorre o Array várias vezes. Em cada passagem, compara elementos adjacentes (vizinhos) e os troca de lugar se estiverem na ordem errada.
- Por que o nome? Porque os maiores elementos flutuam para o final do Array como bolhas de sabão.
- Complexidade: no pior e no caso médio.
🎯 2. Selection Sort (Seleção)
Ele divide o Array em duas partes: a parte ordenada (no início) e a parte desordenada. Ele busca o menor elemento da parte desordenada e o joga para o final da parte ordenada.
- Complexidade: sempre, pois ele sempre precisa varrer o resto do Array para ter certeza de quem é o menor.
4. 📖 Exemplo Guiado: Uma Passada do Bubble Sort
Lista: [5, 2, 9, 1]
- Compara 5 e 2. O 5 é maior? Sim! Troca. →
[2, 5, 9, 1] - Compara 5 e 9. O 5 é maior? Não. Mantém. →
[2, 5, 9, 1] - Compara 9 e 1. O 9 é maior? Sim! Troca. →
[2, 5, 1, 9]
- Fim da primeira passada. O maior número (9) já está na sua posição correta no final!
5. 🛠️ Prática Obrigatória 1: Continuando a Bolha
Com base no exemplo guiado, a lista ficou [2, 5, 1, 9]. O número 9 já está no lugar certo.
- Faça a segunda passada do Bubble Sort nos números restantes (
2, 5, 1) e mostre como a lista fica no final dessa passada.
6. 🛠️ Prática Obrigatória 2: O Pior Caso do Bubble Sort
Se entregarmos uma lista que já está perfeitamente ordenada (ex: [1, 2, 3, 4, 5]) para o algoritmo Bubble Sort tradicional, ele ainda vai fazer comparações ou vai perceber que já está pronto?
7. 📤 Instruções de Entrega (GitHub Desktop + Microsoft Teams)
- Faça o Commit: No GitHub Desktop, digite a mensagem (ex:
Finaliza Capítulo 17 Estruturas de Dados) e clique em Commit to main. - Envie para a Nuvem (Push): Clique em Push origin.
8. 📂 Estrutura de Pastas
mod_09_estruturas_de_dados/
├── capitulos/
│ ├── capitulo_17_ordenacao_simples.md
│ └── codigos/
│ └── cap17/
│ └── bubble_sort.js9. 💡 Checkpoint de Lógica
Se o Bubble Sort e o Selection Sort têm a mesma complexidade , por que o Selection Sort costuma ser um pouco mais rápido na prática? (Dica: Pense no número de vezes que eles trocam os elementos de lugar na memória).
10. 🔥 Desafio de Fixação
Pesquise sobre o algoritmo Insertion Sort (Ordenação por Inserção), que também é um algoritmo simples, mas muito eficiente para listas quase ordenadas.
🔑 Gabarito de Código/Fórmulas
Gabarito da Prática 1:
Segunda passada em [2, 5, 1]:
- Compara 2 e 5. Ordem certa. →
[2, 5, 1] - Compara 5 e 1. Troca! →
[2, 1, 5]
- Fim da segunda passada. A lista completa está
[2, 1, 5, 9]. O 5 e o 9 já estão nos seus lugares.