decoda/docs/edu/recursos/atividades/programacao/ordenacao.md

---
title: Ordenação
sidebar_position: 9
---

# Ordenação

<div style={{ display: "flex", alignItems: "flex-start", gap: "16px", flexWrap: "wrap" }}>
	<img
		src={require("@site/static/images/atividades/programacao/ordenacao-thumbnail.png").default}
		alt="Thumbnail da atividade Ordenação"
		style={{ width: "280px", height: "280px", objectFit: "contain", flexShrink: 0 }}
	/>
	<div style={{ flex: 1, minWidth: "260px" }}>
		<p>Ordenação apresenta um dos problemas mais estudados da computação — colocar uma lista em ordem crescente — e o explora por múltiplos ângulos. O estudante implementa, fase a fase, cinco estratégias diferentes para o mesmo problema e percebe que cada uma tem uma lógica distinta, um custo diferente e situações em que funciona melhor ou pior.</p>
		<p>Ao contrário de atividades que permitem soluções abertas, aqui cada fase exige um algoritmo específico. A validação verifica não só se a lista ficou ordenada, mas se o padrão de execução corresponde ao algoritmo pedido. Isso leva o estudante a entender o que torna cada algoritmo diferente — não apenas a chegar no resultado.</p>
	</div>
</div>

## O que esta atividade ensina sobre programação

Ordenação é um contexto muito fértil para trabalhar estruturas de repetição aninhadas, variáveis de controle e operações sobre listas. Mas o que a distingue das demais atividades é que ela introduz uma ideia central da computação: diferentes algoritmos podem resolver o mesmo problema, com estratégias e custos radicalmente distintos.

Nas fases iniciais, o estudante pratica comparação e troca de dois ou três elementos com condicionais simples — consolidando o básico. A progressão avança para os algoritmos clássicos: **Bubble Sort**, **Selection Sort**, **Insertion Sort**, **Shell Sort** e **Counting Sort**. Cada um representa uma abordagem diferente, dos mais intuitivos aos que fogem completamente do paradigma de comparação direta.

A atividade também é uma porta de entrada concreta para análise de algoritmos. Sem precisar de formalismo matemático, o estudante pode observar quantas operações cada estratégia realiza, comparar resultados e começar a pensar em eficiência — uma competência que vai além da programação e se aplica a qualquer tipo de problema que exige raciocínio sobre custo e escala.

## Os algoritmos

Cada algoritmo desta atividade representa uma estratégia diferente para o mesmo problema. Os diagramas abaixo mostram o fluxo lógico de cada um.

### Bubble Sort

O Bubble Sort percorre a lista repetidamente, comparando pares de elementos adjacentes e trocando os que estão fora de ordem. A cada passada completa, o maior elemento ainda desordenado chega à sua posição final. O processo se repete até que nenhuma troca seja necessária.

```mermaid
flowchart TD
    A[Início] --> B[Nova passada pela lista]
    B --> C[i = 0]
    C --> D{elemento atual maior que o próximo?}
    D -->|Sim| E[Trocar os dois]
    D -->|Não| F[i = i + 1]
    E --> F
    F --> G{Fim da passada?}
    G -->|Não| D
    G -->|Sim| H{Alguma troca ocorreu?}
    H -->|Sim| B
    H -->|Não| I[Lista ordenada]
```

A versão com otimização acrescenta uma variável de controle que detecta quando nenhuma troca ocorreu na passada — o que significa que a lista já está ordenada — encerrando o algoritmo antes das passadas restantes.

#### Quando é vantajoso

O Bubble Sort brilha quando a lista já está quase ordenada: com a otimização de parada antecipada, ele pode terminar em uma única passada, com custo proporcional ao tamanho da lista. É também o algoritmo mais fácil de implementar e depurar, o que o torna o ponto de partida natural para quem está aprendendo ordenação.

#### Quando não é a melhor escolha

Em listas grandes e desordenadas, o Bubble Sort realiza um número quadrático de comparações e trocas — o que o torna impraticável para volumes acima de alguns milhares de elementos. Em performance real, costuma ser o mais lento entre os algoritmos O(n²) porque acumula muitas trocas por passada.

#### Onde é usado

Por seu custo quadrático, o Bubble Sort raramente é escolhido em sistemas reais. Sua importância é quase inteiramente pedagógica: a lógica de "empurrar o maior elemento para o final a cada passada" é uma das mais intuitivas para entender o conceito de ordenação. Versões educacionais e ferramentas de visualização de algoritmos o utilizam amplamente por esse motivo.

### Selection Sort

O Selection Sort divide a lista em duas partes: a porção já ordenada, que cresce da esquerda, e a porção desordenada. A cada passada, o algoritmo varre toda a parte desordenada para encontrar o menor elemento e o posiciona no início dela — com uma única troca por passada.

```mermaid
flowchart TD
    A[i = 0] --> B[mínimo = i]
    B --> C[j = i + 1]
    C --> D{elemento j menor que elemento mínimo?}
    D -->|Sim| E[mínimo = j]
    D -->|Não| F[j = j + 1]
    E --> F
    F --> G{j chegou ao fim?}
    G -->|Não| D
    G -->|Sim| H[Trocar posições i e mínimo]
    H --> I{i chegou ao penúltimo?}
    I -->|Não| J[i = i + 1]
    J --> B
    I -->|Sim| K[Lista ordenada]
```

Uma característica do Selection Sort é que ele realiza exatamente `n - 1` trocas, independente do estado inicial da lista — ao contrário do Bubble Sort, que pode realizar muitas mais.

#### Quando é vantajoso

O Selection Sort é vantajoso quando o custo de escrever na memória é significativamente mais alto do que o de ler — por exemplo, em memórias flash, onde cada escrita tem custo real de desgaste. Nesse contexto, fazer no máximo `n - 1` trocas é uma vantagem concreta. Ele também é simples de implementar e tem comportamento previsível: o número de comparações é sempre o mesmo, independente da entrada.

#### Quando não é a melhor escolha

Assim como o Bubble Sort, o Selection Sort tem custo quadrático no número de comparações — mesmo que a lista já esteja ordenada, ele percorre toda a parte não ordenada a cada passada. Não existe versão com parada antecipada eficaz. Para listas grandes, algoritmos O(n log n) são muito mais eficientes.

#### Onde é usado

O Selection Sort aparece em contextos embarcados com memória muito limitada e escrita cara, como microcontroladores simples e dispositivos EEPROM. Em sistemas de uso geral, é substituído por algoritmos mais eficientes. Pedagogicamente, é valioso porque separa claramente a fase de busca do mínimo da fase de troca, tornando a lógica de duas etapas por passada muito explícita.

### Insertion Sort

O Insertion Sort constrói a lista ordenada de forma incremental. Para cada elemento da parte desordenada, ele retrocede na parte já ordenada deslocando os elementos maiores uma posição para a direita, até encontrar o lugar certo para inserir o elemento atual.

```mermaid
flowchart TD
    A[i = 1] --> B[guardar elemento da posição i]
    B --> C[j = i - 1]
    C --> D{j válido e elemento j maior que o guardado?}
    D -->|Sim| E[Deslocar elemento j uma posição para a direita]
    E --> F[j = j - 1]
    F --> D
    D -->|Não| G[Inserir o guardado na posição j + 1]
    G --> H{i chegou ao fim?}
    H -->|Não| I[i = i + 1]
    I --> B
    H -->|Sim| J[Lista ordenada]
```

O Insertion Sort é muito eficiente para listas quase ordenadas, pois precisa de poucos deslocamentos quando os elementos já estão próximos de sua posição final. É também a base do Shell Sort.

#### Quando é vantajoso

O Insertion Sort é uma das melhores escolhas para listas pequenas (tipicamente abaixo de 20 elementos) ou quase ordenadas. Nesses casos, ele supera algoritmos teoricamente mais eficientes como o Merge Sort, que carregam custo fixo maior de divisão e combinação. Para listas já ordenadas, seu custo é linear — O(n) — pois nenhum deslocamento é necessário.

#### Quando não é a melhor escolha

Em listas grandes e aleatórias, o custo quadrático domina. Cada novo elemento pode precisar ser deslocado até o início da lista, resultando em muitas operações de escrita. Para esses casos, algoritmos O(n log n) são necessários.

#### Onde é usado

O Insertion Sort está presente em implementações híbridas de algoritmos avançados. O Timsort — usado por padrão em Python e na JVM — aplica o Insertion Sort em blocos pequenos antes de combiná-los com Merge Sort. O IntroSort — base do `std::sort` do C++ — também recorre ao Insertion Sort quando a recursão chega a sublistas pequenas. É um algoritmo com papel real e ativo nos sistemas de produção mais difundidos.

### Shell Sort

O Shell Sort é uma generalização do Insertion Sort. Em vez de inserir comparando apenas elementos vizinhos, ele começa comparando elementos separados por um intervalo inicial de metade do tamanho da lista. A cada rodada, esse intervalo é dividido ao meio. Quando o intervalo chega a 1, o comportamento é idêntico ao Insertion Sort — mas a lista já está bem próxima da ordem, então o trabalho restante é mínimo.

```mermaid
flowchart TD
    A[intervalo = tamanho dividido por 2] --> B{intervalo maior ou igual a 1?}
    B -->|Não| Z[Lista ordenada]
    B -->|Sim| C[i = intervalo]
    C --> D[guardar elemento da posição i]
    D --> E[j = i - intervalo]
    E --> F{j válido e elemento j maior que o guardado?}
    F -->|Sim| G[Deslocar elemento j para a posição j + intervalo]
    G --> H[j = j - intervalo]
    H --> F
    F -->|Não| I[Inserir o guardado na posição j + intervalo]
    I --> J{i chegou ao fim?}
    J -->|Não| K[i = i + 1]
    K --> D
    J -->|Sim| L[intervalo = intervalo dividido por 2]
    L --> B
```

A intuição por trás do Shell Sort é que comparações de longa distância movem os elementos para perto de sua posição final muito mais rapidamente do que comparações vizinhas, reduzindo o trabalho das rodadas seguintes.

#### Quando é vantajoso

O Shell Sort é especialmente adequado para sistemas embarcados e ambientes sem suporte a recursão, onde algoritmos O(n log n) baseados em divisão (como Merge Sort e Quick Sort) são difíceis de implementar. Ele entrega desempenho subquadrático — na prática próximo de O(n log n) para sequências de intervalos bem escolhidas — com código iterativo simples e memória O(1).

#### Quando não é a melhor escolha

A complexidade do Shell Sort depende da sequência de intervalos escolhida, e a análise teórica ainda é um problema em aberto para algumas sequências. Em sistemas com suporte a recursão e memória suficiente, o Merge Sort ou o Timsort oferecem garantias mais sólidas e melhor desempenho em listas grandes.

#### Onde é usado

O Shell Sort é encontrado em firmwares, sistemas operacionais compactos e ambientes com pilha de chamadas limitada. O kernel do Linux e o uClibc utilizaram implementações de Shell Sort em contextos onde simplicidade e ausência de recursão eram mais importantes do que performance máxima. É também um ponto de passagem didático natural entre o Insertion Sort e os algoritmos baseados em divisão.

### Counting Sort

O Counting Sort é fundamentalmente diferente dos anteriores: ele **não compara elementos entre si**. Em vez disso, conta quantas vezes cada valor aparece na lista e, a partir dessas contagens, reconstrói a lista já ordenada. Por isso, ele escapa do limite teórico inferior O(n log n) que vale para qualquer algoritmo baseado em comparação.

```mermaid
flowchart TD
    A[Criar lista de contagem com zeros] --> B[Para cada elemento da lista]
    B --> C[Incrementar a contagem do valor correspondente]
    C --> D{Todos os elementos contados?}
    D -->|Não| B
    D -->|Sim| E[v = 0]
    E --> F{v menor que tamanho da contagem?}
    F -->|Não| G[Lista reconstruída]
    F -->|Sim| H{contagem de v maior que zero?}
    H -->|Não| I[v = v + 1]
    I --> F
    H -->|Sim| J[Adicionar v à próxima posição da lista]
    J --> K[Decrementar contagem de v]
    K --> H
```

#### Quando é vantajoso

O Counting Sort tem complexidade O(n + k), onde **k** é o valor máximo dos dados. Quando k é pequeno em relação a n, ele supera qualquer algoritmo de comparação: ordenar um milhão de notas escolares no intervalo 0–10 é muito mais rápido com Counting Sort do que com Bubble, Insertion ou até Merge Sort.

Ele também é a base do **Radix Sort**, que o aplica dígito a dígito para ordenar inteiros arbitrários em O(d · n), onde d é o número de dígitos.

#### Quando não é a melhor escolha

Quando k >> n — por exemplo, ordenar 10 números no intervalo [0, 1.000.000] — o algoritmo aloca um array de 1 milhão de posições desnecessariamente, com memória O(k) dominando o custo. Além disso, o Counting Sort não se aplica diretamente a dados com ponto flutuante, strings ou objetos complexos, nem a dados com distribuição desconhecida ou muito esparsa.

#### Comparação de complexidade

| Algoritmo | Tempo médio | Memória |
|---|---|---|
| Bubble / Insertion | O(n²) | O(1) |
| Merge / Heap | O(n log n) | O(n) / O(1) |
| Quick Sort | O(n log n) | O(log n) |
| Counting Sort | O(n + k) | O(k) |

Nas fases desta atividade, a lista tem 10 valores com máximo 55. O Counting Sort usa um array de 56 posições — mais memória do que o estritamente necessário para n=10, mas eficiente caso houvesse muitos elementos nessa faixa. Sua importância aqui é pedagógica: ilustrar que existem algoritmos que exploram propriedades dos dados para escapar do limite O(n log n), ao custo de restrições sobre o tipo e a faixa dos valores.

#### Onde é usado

O Counting Sort aparece como subroutine do **Radix Sort**, que o aplica dígito a dígito para ordenar inteiros de qualquer magnitude. Sistemas de contagem de votos, classificação de idades, notas ou qualquer dado inteiro com faixa pequena e conhecida são contextos naturais. Implementações de ordenação estável em sistemas de banco de dados também o utilizam quando os dados satisfazem as restrições de tipo e faixa. No ecossistema de algoritmos, ele representa a categoria dos algoritmos não comparativos — junto com o Radix Sort e o Bucket Sort — que quebram o limite teórico O(n log n) ao explorar a estrutura interna dos dados.

## Mediação pedagógica

Uma abordagem eficaz é pedir que o estudante descreva o algoritmo em palavras antes de implementá-lo em blocos. "O que o Bubble Sort faz a cada passada?" ou "Como o Selection Sort escolhe o próximo elemento?" ajudam a separar a compreensão do algoritmo da habilidade de montá-lo. Se o estudante trava nos blocos, o problema está quase sempre na compreensão do algoritmo — não na ferramenta.

Outro recurso valioso é comparar soluções após a implementação. Dois algoritmos que produzem o mesmo resultado final podem ter realizado quantidades muito diferentes de operações. Perguntar "qual deles você acha que fez mais trabalho?" e em seguida observar o número de comparações e trocas — disponíveis nos dados de execução — torna a noção de eficiência concreta e baseada em evidência.

O Shell Sort e o Counting Sort merecem atenção especial na mediação. O Shell Sort exige que o estudante entenda por que comparar elementos distantes pode ser útil antes de comparar os vizinhos — uma ideia contraintuitiva que vale explorar antes de implementar. O Counting Sort, por sua vez, rompe com o modelo mental de "comparar e decidir" e pode gerar uma boa discussão sobre o que é realmente necessário para ordenar uma lista quando se conhece o intervalo dos dados.

## Progressão das fases

| Fase | Nome | O que o estudante pratica |
|---|---|---|
| 1 | Ordenar 2 Números | usar condicional para comparar e trocar dois valores |
| 2 | Ordenar 3 Números | combinar repetição e condicionais para ordenar três elementos |
| 3 | Bubble Sort | comparar pares adjacentes em passadas repetidas |
| 4 | Bubble Sort com Otimização | adicionar controle de parada antecipada quando não há trocas |
| 5 | Selection Sort | encontrar o mínimo da parte desordenada e posicioná-lo com uma troca |
| 6 | Insertion Sort | inserir cada elemento na posição correta deslocando os maiores |
| 7 | Shell Sort | usar comparações com intervalo variável que diminui progressivamente até 1 |
| 8 | Counting Sort | contar ocorrências e reconstruir a lista sem comparar elementos |

## Quando usar

Ordenação é indicada quando a turma já tem fluência com laços, variáveis e condicionais, e está pronta para um problema com múltiplas soluções corretas e eficiências distintas. É especialmente adequada em aulas que queiram discutir análise de algoritmos de forma introdutória, ou que queiram mostrar que a escolha da estratégia depende das características dos dados — não apenas da correção do resultado.

A atividade funciona bem como continuação natural após Cripto, já que ambas trabalham com transformação sistemática de informação regida por regras precisas. Se o objetivo incluir conceitos como memória auxiliar, troca entre espaço e tempo, ou a categoria de algoritmos não comparativos, o Counting Sort oferece um gancho concreto e didático para essa discussão.

## Referências

- Algoritmos de ordenação: https://pt.wikipedia.org/wiki/Algoritmo_de_ordena%C3%A7%C3%A3o
- Bubble Sort: https://pt.wikipedia.org/wiki/Bubble_sort
- Selection Sort: https://pt.wikipedia.org/wiki/Selection_sort
- Insertion Sort: https://pt.wikipedia.org/wiki/Insertion_sort
- Shell Sort: https://pt.wikipedia.org/wiki/Shell_sort
- Counting Sort: https://pt.wikipedia.org/wiki/Counting_sort
- Complexidade computacional: https://pt.wikipedia.org/wiki/Complexidade_computacional