Aplicações Informáticas B · 12.º Ano · Algoritmia e Estruturas de Dados · 1o Periodo

Algoritmos de Ordenação

Os alunos implementam e comparam algoritmos de ordenação como Bubble Sort, Selection Sort e Insertion Sort.

• Aprendizagens Essenciais
• DGE: Secundário - Algoritmia e Programação
• DGE: Secundário - Pensamento Computacional

Sobre este tópico

Os algoritmos de ordenação organizam conjuntos de dados de forma eficiente, essencial em algoritmia. Neste tópico, os alunos do 12.º ano implementam e comparam Bubble Sort (Ordenação por Bolhas), Selection Sort (por Seleção) e Insertion Sort (por Inserção). Estes algoritmos simples baseiam-se em trocas e comparações sucessivas, permitindo analisar o número de operações em listas de números ou strings.

No âmbito do Currículo Nacional, este conteúdo pertence à unidade de Algoritmia e Estruturas de Dados, alinhado com os standards de Algoritmia e Programação e Pensamento Computacional no secundário. Os alunos avaliam a performance em dados variados, como listas ordenadas ou aleatórias, analisam vantagens e desvantagens face a algoritmos complexos como Quick Sort, e explicam o impacto na experiência do utilizador em aplicações reais, como pesquisas em bases de dados.

Abordagens ativas beneficiam este tópico porque a codificação prática, medição de tempos de execução e visualização de passos tornam conceitos abstratos como complexidade temporal O(n²) concretos. Quando os alunos implementam, testam em datasets crescentes e discutem resultados em grupo, internalizam diferenças de eficiência e desenvolvem competências de otimização.

Questões-Chave

1. Avalie a performance de diferentes algoritmos de ordenação em conjuntos de dados variados.
2. Analise as vantagens e desvantagens de algoritmos de ordenação simples versus complexos.
3. Explique como a escolha do algoritmo de ordenação pode afetar a experiência do utilizador.

Objetivos de Aprendizagem

• Comparar a eficiência temporal (complexidade O(n²)) dos algoritmos Bubble Sort, Selection Sort e Insertion Sort em listas de tamanhos variados.
• Analisar as vantagens e desvantagens de cada algoritmo de ordenação simples em termos de número de comparações e trocas.
• Implementar os algoritmos Bubble Sort, Selection Sort e Insertion Sort em Python, demonstrando a sua funcionalidade.
• Explicar como a escolha de um algoritmo de ordenação pode impactar o desempenho de uma aplicação de pesquisa de dados.

Antes de Começar

Introdução à Programação com Python

Porquê: Os alunos precisam de saber declarar variáveis, usar estruturas de controlo (if, for, while) e manipular listas para implementar os algoritmos.

Conceitos Fundamentais de Algoritmos

Porquê: É necessário compreender o que é um algoritmo, a importância da sequência de passos e a ideia de resolução de problemas para abordar algoritmos de ordenação.

Vocabulário-Chave

Bubble Sort	Um algoritmo de ordenação simples que percorre repetidamente a lista, compara elementos adjacentes e troca-os se estiverem na ordem errada. É conhecido pela sua simplicidade, mas ineficiência em grandes conjuntos de dados.
Selection Sort	Um algoritmo de ordenação que divide a lista em duas partes: uma ordenada e outra desordenada. Repetidamente encontra o menor elemento na parte desordenada e coloca-o no final da parte ordenada.
Insertion Sort	Um algoritmo de ordenação que constrói a lista final ordenada um item de cada vez. É mais eficiente em listas que já estão parcialmente ordenadas.
Complexidade Temporal	Uma medida que descreve o tempo de execução de um algoritmo em função do tamanho da entrada (n). Algoritmos com complexidade O(n²) tornam-se significativamente mais lentos à medida que n aumenta.

Atenção a estes erros comuns

Erro comum

Todos os algoritmos de ordenação têm a mesma eficiência independentemente do tamanho dos dados.

O que ensinar em alternativa

Estes algoritmos simples são O(n²) no pior caso, o que se revela em testes com listas grandes. Abordagens ativas como medições em grupo com datasets variados ajudam os alunos a visualizar o crescimento quadrático e a comparar empiricamente.

Erro comum

O Bubble Sort é o mais rápido porque faz muitas trocas rápidas.

O que ensinar em alternativa

Na verdade, as trocas excessivas tornam-no ineficiente. Implementações práticas em pares mostram que Insertion Sort é melhor em listas quase ordenadas, fomentando discussões que corrigem modelos mentais errados.

Erro comum

A complexidade espacial importa mais que a temporal na ordenação.

O que ensinar em alternativa

Estes algoritmos usam O(1) espaço extra, priorizando tempo. Experiências de codificação e análise de gráficos em turma destacam isso, ajudando alunos a priorizar métricas corretas.

Ideias de aprendizagem ativa

Ensino pelos Pares: Codificação do Bubble Sort

Em pares, os alunos escrevem código em Python para implementar Bubble Sort numa lista de 20 elementos aleatórios. Contam o número de trocas e comparações. Testam com lista já ordenada e registam diferenças.

25 min·Pares

Pequenos Grupos: Comparação de Tempos

Grupos de quatro implementam Selection Sort e Insertion Sort. Executam em listas de tamanhos 100, 500 e 1000 elementos. Medem tempos com timeit e constroem gráfico comparativo.

45 min·Pequenos grupos

Turma: Debate de Escolhas

A turma discute em plenário casos reais, como ordenação em e-commerce. Votam no melhor algoritmo por cenário e justificam com dados das atividades anteriores.

30 min·Turma inteira

Individual: Otimização Pessoal

Cada aluno modifica um algoritmo para dados quase ordenados. Testa performance e propõe uma melhoria simples, registando antes/depois em relatório curto.

20 min·Individual

Ligações ao Mundo Real

• Desenvolvedores de software utilizam estes algoritmos como base para entender a otimização. Por exemplo, ao criar um sistema de gestão de inventário numa loja de retalho, a ordenação eficiente de produtos por preço ou nome é crucial para uma rápida consulta pelo cliente ou funcionário.
• Em aplicações de bases de dados, como as usadas por bibliotecas para catalogar livros, a ordenação é fundamental. Embora algoritmos mais avançados sejam usados em produção, a compreensão de algoritmos simples ajuda a prever gargalos de desempenho em consultas de dados menos comuns ou em bases de dados de menor dimensão.

Ideias de Avaliação

Verificação Rápida

Apresente aos alunos um pequeno conjunto de dados (ex: 5 números). Peça-lhes para descreverem os passos exatos que o algoritmo Selection Sort seguiria para ordenar esses números, focando-se nas trocas e comparações.

Questão para Discussão

Coloque a seguinte questão para discussão em pequenos grupos: 'Se tivessem de ordenar uma lista de 1000 nomes de utilizadores que já se encontra 80% ordenada, qual dos algoritmos (Bubble, Selection, Insertion) escolheriam e porquê? Justifiquem a vossa escolha com base nas características de cada um.'

Bilhete de Saída

Entregue a cada aluno um pedaço de papel. Peça-lhes para escreverem o nome de um algoritmo de ordenação simples, uma frase que descreva a sua principal desvantagem e um cenário onde ele poderia ser aceitável de usar.

Perguntas frequentes

Quais as diferenças entre Bubble Sort, Selection Sort e Insertion Sort?

O Bubble Sort faz trocas adjacentes sucessivas até não haver mais. Selection Sort procura o mínimo e troca com o início. Insertion Sort insere elementos na posição correta numa sublista ordenada. Implementações práticas revelam que Insertion é eficiente em listas pequenas ou quase ordenadas, enquanto os outros lutam com dados aleatórios grandes, com todos em O(n²) pior caso.

Como avaliar a performance de algoritmos de ordenação?

Meça tempo de execução com funções como timeit em Python, para listas de tamanhos variados e tipos de dados (aleatórios, ordenados, reversos). Conte trocas e comparações. Gráficos de tempo vs. n mostram crescimento quadrático, ajudando a comparar e escolher o algoritmo adequado por cenário.

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

A codificação em pares, testes com datasets reais e visualizações de passos (como animações em Processing) tornam a complexidade temporal tangível. Discussões em grupo sobre resultados de medições corrigem intuições erradas e promovem análise crítica. Estas abordagens aumentam retenção em 30-50%, segundo estudos, preparando para algoritmos avançados.

Como a escolha do algoritmo afeta a experiência do utilizador?

Algoritmos lentos em grandes dados causam atrasos em apps, frustrando utilizadores, como em pesquisas de e-commerce. Escolher Insertion para listas pequenas melhora responsividade. Análises de casos reais em aula mostram que otimização temporal eleva usabilidade, ligando teoria a impactos práticos em software quotidiano.