Sorting Algorithms · Algoritmos de Ordenação
| English | Português |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | Ordenação |
| selection sort/sɪˈlekʃn sɔːt/ | ordenação por seleção |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | ordenação por inserção |
| in place/ɪn pleɪs/ | in place |
Putting things in order
- Sorting 排序 rearranges elements into order (smallest to largest, say).
- The AP course covers two simple sorts: selection sort 选择排序 and insertion sort 插入排序.
- Both use nested loops and swap or shift elements into place.
- Sorting first is what lets you use fast binary search afterwards.
Colocando as coisas em ordem
- Ordenar 排序 rearranja elementos em ordem (do menor para o maior, por exemplo).
- O curso AP cobre duas ordenações simples: selection sort 选择排序 e insertion sort 插入排序.
- 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
- Find the smallest remaining element and swap it to the front.
- Then find the smallest of what's left, swap it into the next spot, and so on.
- The front of the array grows sorted; the back shrinks unsorted.
- One swap per pass — but it still scans the rest each pass.
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.
Insertion sort
- Take the next element and shift it back into its correct place among the already-sorted front.
- Like sorting a hand of cards: slot each new card where it belongs.
- The sorted region grows by one each pass.
- Fast when the data is already nearly sorted.
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.
How much work
- Both sorts use nested loops, so they do about
n²comparisons in the worst case. - That's fine for small arrays but slow for very large ones.
- They sort in place 原地 — no second array needed.
- The exam wants you to trace them, not just name them.
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 ordenam no local 原地 — sem necessidade de segundo array.
- O exame quer que você os rastreie, não apenas os nomeie.
Selection sort SWAPS the smallest remaining element to the front; insertion sort SHIFTS each new element back into the sorted part — don't mix them up. Both are O(n²) nested-loop sorts and both sort in place. Trace them step by step (the AP exam asks for the array's state after each pass), rather than memorising a name.
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 on [3, 1, 2]:
- Pass 1: smallest is
1; swap to front →[1, 3, 2]. - Pass 2: smallest of
[3, 2]is2; swap →[1, 2, 3]. - Sorted — the front grew one element per pass.
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.
Sorting orders elements. Selection sort repeatedly swaps the smallest remaining element to the front; insertion sort shifts each new element back into the sorted part. Both are nested-loop, in-place, O(n²) sorts. Sorting enables fast binary search afterwards.
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.
Stepping through a sort · Passando por uma ordenação
Each pass places one more element in order. · Cada passada coloca mais um elemento em ordem.
Selection sort works by... · O selection sort funciona através de...
Selection sort selects the minimum and swaps it forward. · O selection sort seleciona o mínimo e o troca para frente.
Insertion sort works by... · O insertion sort funciona através de...
Insertion sort inserts each element into its sorted place. · O insertion sort insere cada elemento em seu lugar ordenado.
In the worst case, both sorts do about... · No pior caso, ambas as ordenações fazem cerca de...
Nested loops give O(n²). · Laços aninhados dão O(n²).
Both selection and insertion sort work in place (no second array). · Tanto o selection quanto o insertion sort funcionam in-place (sem segundo array).
They rearrange the same array. · Elas reorganizam o mesmo array.
Order the passes of selection sort on [3, 1, 2]. · Ordene as passadas do selection sort em [3, 1, 2].
Front grows sorted, one element per pass. · A frente cresce ordenada, um elemento por passada.
Sorting first is useful because it lets you later use... · Ordenar primeiro é útil porque permite que você use depois...
Binary search needs sorted data. · A busca binária precisa de dados ordenados.