Algoritmos de Ordenação
Introduzido| English | Significado |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | Sorting: ordenação |
| selection sort/sɪˈlekʃn sɔːt/ | selection sort: seleção |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | insertion sort: inserção |
| in place/ɪn pleɪs/ | in situ |
Colocando as coisas em ordem
- Ordenação rearranja elementos em ordem (do menor para o maior, por exemplo).
- O curso AP cobre duas ordenações simples: ordenação por seleção e ordenação por inserção.
- Ambas usam loops aninhados e trocam ou deslocam elementos para o lugar certo.
- Ordenar primeiro é o que permite usar a rápida pesquisa binária depois.
Selection sort
- Encontre o elemento restante menor e troque para a frente.
- Depois encontre o menor do que resta, troque-o para o próximo espaço, e assim por diante.
- A frente do array cresce ordenada; a parte traseira diminui desordenada.
- Uma troca por passagem — mas ainda escaneia o resto a cada passagem.

Uma ordenação por inserção, deslocando cada chave para o lugar certo, passada após passada
Insertion sort
- Pegue o próximo elemento e desloque-o para trás em seu lugar correto entre a parte frontal já ordenada.
- Como organizar uma mão de cartas: coloque cada nova carta onde ela pertence.
- A região ordenada cresce de um elemento a cada passagem.
- Rápido quando os dados estão quase já ordenados.
Quanto trabalho
- Ambas as ordenações usam loops aninhados, então fazem cerca de
n²comparações no pior caso. - Isso é bom para arrays pequenos, mas lento para muito grandes.
- Elas realizam a ordenação no local — sem necessidade de um segundo array.
- O exame quer que você os rastreie, não apenas os nomeie.
Selection sort TROCA o elemento restante menor para a frente; insertion sort DESLOCA cada novo elemento para trás na parte ordenada — não os confunda. Ambos são ordenações de loop aninhado O(n²) e ambas ordenam no local. Rastreie-as passo a passo (o exame AP pede o estado do array após cada passagem), em vez de memorizar um nome.
Selection sort em [3, 1, 2]:
- Passagem 1: o menor é
1; troque para a frente →[1, 3, 2]. - Passagem 2: o menor de
[3, 2]é2; troque →[1, 2, 3]. - Ordenado — a frente cresceu um elemento por passagem.
Ordenar coloca elementos em ordem. Selection sort repete a troca do elemento restante menor para a frente; insertion sort desloca cada novo elemento para trás na parte ordenada. Ambas são ordenações de loop aninhado, no local, O(n²). A ordenação permite a rápida pesquisa binária depois.
Passando por uma ordenação
Cada passada coloca mais um elemento em ordem.
O selection sort funciona através de...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
O selection sort seleciona o mínimo e o troca para frente.
O insertion sort funciona através de...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
O insertion sort insere cada elemento em seu lugar ordenado.
No pior caso, ambas as ordenações fazem cerca de...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Laços aninhados dão O(n²).
Tanto o selection quanto o insertion sort funcionam in-place (sem segundo array).
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Elas reorganizam o mesmo array.
Ordene as passadas do selection sort em [3, 1, 2].
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
A frente cresce ordenada, um elemento por passada.
Ordenar primeiro é útil porque permite que você use depois...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
A busca binária precisa de dados ordenados.