Informática · 11.º Ano · Algoritmia e Estruturas de Dados Complexas · 1o Periodo

Algoritmos de Ordenação Básicos

Os alunos estudam e implementam algoritmos de ordenação como Bubble Sort, Selection Sort e Insertion Sort, comparando a sua eficiência.

• Aprendizagens Essenciais
• DGE: Secundário - Algoritmia
• DGE: Secundário - Resolução de Problemas

Sobre este tópico

Os algoritmos de ordenação básicos, como Bubble Sort, Selection Sort e Insertion Sort, ensinam os alunos a organizar listas de dados através de trocas e comparações iterativas. No 11.º ano, implementam estes algoritmos em programação, medem o número de operações e comparam a eficiência para diferentes tamanhos de conjuntos de dados. Esta prática responde às questões chave do currículo nacional, como medir objetivamente o melhor algoritmo e justificar escolhas com base na complexidade temporal O(n²) comum a estes métodos.

Na unidade de Algoritmia e Estruturas de Dados Complexas, o tópico fortalece o pensamento computacional avançado e a resolução de problemas, ligando teoria à execução prática. Os alunos observam como o Bubble Sort faz múltiplas passagens pela lista, o Selection Sort procura mínimos e o Insertion Sort insere elementos ordenados, preparando-os para estruturas mais eficientes.

A aprendizagem ativa beneficia este tópico porque implementações hands-on e simulações em código tornam a complexidade abstracta concreta e mensurável. Quando os alunos cronometram execuções em grupo e visualizam animações, internalizam diferenças de performance intuitivamente, melhorando a retenção e a aplicação em problemas reais.

Questões-Chave

1. Como podemos medir objetivamente qual o melhor algoritmo para um conjunto específico de dados?
2. Compare a complexidade temporal dos algoritmos de ordenação básicos.
3. Justifique a escolha de um algoritmo de ordenação específico para um pequeno conjunto de dados.

Objetivos de Aprendizagem

• Implementar e demonstrar o funcionamento dos algoritmos Bubble Sort, Selection Sort e Insertion Sort para ordenar listas de números.
• Comparar a complexidade temporal (O(n²)) dos algoritmos Bubble Sort, Selection Sort e Insertion Sort através da contagem de operações.
• Analisar o desempenho de cada algoritmo de ordenação com diferentes tamanhos de conjuntos de dados e justificar a sua escolha.
• Explicar as diferenças fundamentais entre os métodos de comparação e troca em cada um dos algoritmos estudados.

Antes de Começar

Introdução à Programação e Variáveis

Porquê: Os alunos precisam de compreender como declarar e manipular variáveis para implementar os algoritmos.

Estruturas de Controlo (Ciclos For e While)

Porquê: A implementação destes algoritmos depende fortemente do uso de ciclos para iterar sobre os elementos da lista.

Listas e Arrays

Porquê: Os algoritmos de ordenação operam sobre coleções de dados, sendo essencial o conhecimento de como aceder e modificar elementos em listas ou arrays.

Vocabulário-Chave

Bubble Sort	Um algoritmo de ordenação simples que compara repetidamente pares de elementos adjacentes e troca-os se estiverem na ordem errada. Percorre a lista várias vezes até que esteja ordenada.
Selection Sort	Um algoritmo de ordenação que divide a lista em duas partes: uma sublista ordenada e uma sublista não ordenada. Repetidamente encontra o menor elemento da sublista não ordenada e coloca-o no final da sublista ordenada.
Insertion Sort	Um algoritmo de ordenação que constrói a lista final ordenada um item de cada vez. Assume que os primeiros elementos da lista estão ordenados e insere cada elemento subsequente na posição correta dentro da parte já ordenada.
Complexidade Temporal	Uma medida que descreve o tempo de execução de um algoritmo em função do tamanho da entrada (n). Para estes algoritmos, é tipicamente O(n²).
Troca (Swap)	A operação fundamental em muitos algoritmos de ordenação que envolve a troca das posições de dois elementos numa lista.

Atenção a estes erros comuns

Erro comum

O Bubble Sort é sempre o mais rápido por fazer trocas imediatas.

O que ensinar em alternativa

Na verdade, faz muitas trocas desnecessárias em listas grandes, levando a O(n²). Abordagens ativas como cronometrar execuções em pares ajudam os alunos a verem o impacto real e a corrigirem esta ideia através de dados próprios.

Erro comum

A complexidade temporal depende só do tamanho da lista, ignorando o tipo de dados.

O que ensinar em alternativa

Insertion Sort é melhor em listas quase ordenadas. Simulações em pequenos grupos com dados variados revelam estas nuances, promovendo discussões que clarificam o papel do input na eficiência.

Erro comum

Todos os algoritmos básicos são adequados para grandes volumes de dados.

O que ensinar em alternativa

A sua O(n²) torna-os ineficientes para n grande. Torneios em turma com listas crescentes mostram falhas práticas, ajudando os alunos a justificarem escolhas futuras.

Ideias de aprendizagem ativa

Ensino pelos Pares: Codificação de Bubble Sort

Os alunos em pares escrevem o código do Bubble Sort para ordenar listas de 20 números aleatórios. Contam manualmente as trocas e comparações em papel antes de executar no computador. Discutem o padrão de passes múltiplos observados.

30 min·Pares

Pequenos Grupos: Corrida de Selection Sort

Grupos geram listas de tamanhos crescentes (10, 50, 100 elementos) e implementam Selection Sort. Cronometram a execução e registam tempos numa tabela partilhada. Analisam o crescimento quadrático dos tempos.

45 min·Pequenos grupos

Turma: Torneio de Insertion Sort

A turma divide-se em equipas para codificar Insertion Sort e competir em ordenação de listas geradas aleatoriamente. Cada equipa apresenta o código e resultados de eficiência. Votam no mais claro e eficiente.

50 min·Turma inteira

Individual: Simulação Visual de Algoritmos

Cada aluno usa uma ferramenta online para simular os três algoritmos em listas variáveis. Regista observações sobre trocas e destaca diferenças visuais. Partilha num mural digital da turma.

25 min·Individual

Ligações ao Mundo Real

• A organização de listas de contactos num telemóvel ou de ficheiros num computador por ordem alfabética ou cronológica utiliza princípios de ordenação. Embora algoritmos mais eficientes sejam usados em sistemas operativos, a lógica subjacente é semelhante.
• Em bases de dados, a ordenação de resultados de pesquisa é crucial para a experiência do utilizador. Por exemplo, ao procurar voos num site de viagens, a apresentação por preço ou hora de partida depende de algoritmos de ordenação eficientes.

Ideias de Avaliação

Verificação Rápida

Apresente aos alunos uma pequena lista de números (ex: [5, 1, 4, 2, 8]). Peça-lhes para escreverem, passo a passo, como o Selection Sort ordenaria esta lista, indicando o elemento mínimo encontrado em cada iteração e a troca realizada.

Bilhete de Saída

Entregue a cada aluno um pedaço de papel. Peça-lhes para escreverem o nome de um dos três algoritmos de ordenação estudados e uma frase que justifique por que razão esse algoritmo pode ser mais ou menos eficiente que os outros para um conjunto de dados específico (ex: dados já quase ordenados).

Questão para Discussão

Coloque a seguinte questão no quadro: 'Se tivéssemos de ordenar 100.000 números, qual dos algoritmos básicos (Bubble, Selection, Insertion) seria a pior escolha e porquê?'. Incentive os alunos a responderem com base na complexidade temporal e no número de operações.

Perguntas frequentes

Qual a complexidade temporal dos algoritmos Bubble Sort, Selection Sort e Insertion Sort?

Todos exibem complexidade temporal média O(n²) no pior caso, com Bubble Sort a realizar trocas adjacentes, Selection Sort a seleccionar mínimos e Insertion Sort a inserir elementos. Os alunos devem medir com testes práticos em listas de tamanhos variados para confirmar o crescimento quadrático e ligar à notação Big O do currículo.

Como comparar a eficiência prática de algoritmos de ordenação básicos?

Implemente os algoritmos em Python, gere listas aleatórias de 10 a 1000 elementos e cronometre execuções. Registe tempos e trocas numa tabela. Esta análise revela padrões como o Insertion Sort ser mais rápido em listas pequenas ou quase ordenadas, justificando escolhas baseadas em dados reais.

Como a aprendizagem ativa ajuda a entender algoritmos de ordenação?

Actividades hands-on, como codificar e simular em pares ou grupos, tornam conceitos abstractos de complexidade visíveis através de tempos reais e animações. Discussões colaborativas após torneios de turma reforçam comparações, melhoram a retenção e desenvolvem resolução de problemas, alinhando com o pensamento computacional avançado do 11.º ano.

Para que tipo de dados escolher Insertion Sort em vez de Bubble Sort?

Prefira Insertion Sort para listas pequenas ou quase ordenadas, pois faz menos trocas ao inserir elementos no subconjunto ordenado. Testes em sala com inputs reais mostram a sua vantagem prática sobre o Bubble Sort, que repete passes completos desnecessariamente, ajudando a justificar decisões no contexto da unit.