🚀 Capítulo 18: Algoritmos de Ordenação Avançados (Tema: Naruto)
NOTE
Este capítulo utiliza a temática de Naruto para explicar os algoritmos de ordenação avançados. O Jutsu Multi-Clones das Sombras é a metáfora perfeita para a estratégia de “Dividir para Conquistar”!
1. 🎯 Objetivo da Aula
Compreender o funcionamento dos algoritmos de ordenação avançados: Merge Sort e Quick Sort, entendendo a estratégia de “Dividir para Conquistar” e por que eles são muito mais rápidos () que os métodos simples.
2. 🏢 O Cenário Prático (Seu Desafio)
Para a fase final do Exame Chunin, o Hokage precisa ordenar uma lista de 1.000 ninjas por nível de poder.
- Se usarmos o Bubble Sort do Sonic (Capítulo anterior), o computador vai demorar muito tempo (1.000.000 de operações!).
- Precisamos de um jutsu mais avançado. O Naruto sugere usar o Jutsu Multi-Clones das Sombras para dividir o trabalho!
Seu desafio é entender como os algoritmos Merge Sort e Quick Sort dividem o problema para conquistar a resposta muito mais rápido!
3. 🧠 Fundamentos: A Teoria Traduzida
Ambos os algoritmos usam o paradigma de Dividir para Conquistar:
- Dividir: Quebra o problema grande em subproblemas menores.
- Conquistar: Resolve os subproblemas menores (geralmente usando recursão).
- Combinar: Junta as soluções dos subproblemas para obter a solução final.
🧩 1. Merge Sort (Ordenação por Intercalação)
Ele divide o Array ao meio repetidamente até que cada parte tenha apenas 1 elemento (um Array de 1 elemento já está ordenado!). Depois, ele vai juntando (intercalando) as partes de volta, já na ordem certa.
- Complexidade: sempre (no melhor, pior e caso médio). Gasta memória extra para criar os sub-arrays.
⚡ 2. Quick Sort (Ordenação Rápida)
Ele escolhe um elemento do Array para ser o Pivô. Ele rearranja o Array de modo que todos os elementos menores que o pivô fiquem à sua esquerda, e os maiores à sua direita. Depois, ele repete o processo recursivamente para as duas metades.
- Complexidade: no caso médio. É o mais rápido na prática e não gasta memória extra. No pior caso (se escolher um pivô ruim), pode cair para .
4. 📖 Exemplo Guiado: O Merge Sort na Prática
Lista original: [4, 2, 1, 3]
- Divide:
[4, 2]e[1, 3] - Divide de novo:
[4],[2],[1],[3] - Combina ordenando:
[2, 4]e[1, 3] - Combina tudo: Compara o 2 com o 1 (1 é menor), depois o 2 com o 3 (2 é menor)… Resultado:
[1, 2, 3, 4].
5. 🛠️ Prática Obrigatória 1: Escolhendo o Pivô
No algoritmo Quick Sort, o que acontece se escolhermos sempre o menor número do Array como pivô? Isso é bom ou ruim para a velocidade do algoritmo?
6. 🛠️ Prática Obrigatória 2: Memória vs Velocidade
O Merge Sort é garantido que vai demorar , mas ele precisa criar cópias dos arrays na memória para funcionar. Se você estivesse programando um chip de um brinquedo com pouquíssima memória RAM, você escolheria o Merge Sort ou o Quick Sort?
7. 📤 Instruções de Entrega (GitHub Desktop + Microsoft Teams)
- Faça o Commit: No GitHub Desktop, digite a mensagem (ex:
Finaliza Capítulo 18 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_18_ordenacao_avancada.md
│ └── codigos/
│ └── cap18/
│ └── merge_sort.js9. 💡 Checkpoint de Lógica
Por que é muito melhor do que para listas grandes? (Dica: Para , , enquanto ).
10. 🔥 Desafio de Fixação
Pesquise o que é a Recursão (uma função que chama a si mesma) e como ela é essencial para o funcionamento do Merge e do Quick Sort.
🔑 Gabarito de Código/Fórmulas
Gabarito da Prática 1: É ruim! Se escolhermos sempre o menor (ou o maior), a divisão não será ao meio, mas sim de 1 elemento contra o resto. O algoritmo vai se degradar e virar , igual ao Bubble Sort. Gabarito da Prática 2: Escolheria o Quick Sort, pois ele opera diretamente no Array original (in-place) e não gasta memória extra.