Sorting algorithms
Introduzido| English | Significado |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | ordenação por bolha |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | ordenação por inserção |
| in place/ɪn pleɪs/ | no local |
| stable/ˈsteɪbl/ | estável |
A ordenação que é lenta à propósito
- Todas as bibliotecas sérias usam um algoritmo de ordenação que nenhum exame pede para você escrever. Bubble sort e insertion sort são ambos $O(n^2)$, e ambos são superados por qualquer boa ordenação em uma lista grande.
- Elas estão no programa de estudos de qualquer forma, e por uma boa razão: são curtas o suficiente para serem rastreadas à mão, e rastrear uma é como você aprende o que uma ordenação realmente faz com um array.
- Existe também um caso real para a insertion sort. Em uma lista pequena ou quase ordenada, ela é genuinamente a mais rápida disponível, e bibliotecas reais alternam para ela exatamente nesses casos.
- Esta lição trata de bubble sort 冒泡排序 e insertion sort 插入排序: os algoritmos, seu comportamento e onde cada um vence.
Ordenação bolha (Bubble sort)
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
swap A[i], A[i + 1]
swapped ← TRUE
ENDIF
NEXT i
IF NOT swapped THEN // already sorted
EXIT FOR
ENDIF
NEXT pass
- Cada passagem compara pares adjacentes e troca quaisquer que estejam fora de ordem, então o maior valor restante "borbulha" para o final.
- Após a passagem $k$, os últimos $k$ elementos estão definidos, é por isso que o loop interno para em $n - \text{pass}$.
- A bandeira
swappedpermite que ele pare cedo: se uma passagem inteira não faz nenhuma troca, a lista está ordenada.
Insertion sort
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j] // shift right
j ← j - 1
ENDWHILE
A[j + 1] ← key // drop it in
NEXT i
- Ele constrói uma seção ordenada na frente, crescendo de um em cada vez. Cada novo elemento é mantido de lado como
key, elementos maiores são movidos para a direita para abrir espaço, e a chave é inserida. - É assim que a maioria das pessoas ordena um baralho de cartas, que é a analogia esperada no exame.

A esquerda está ordenada, a direita intocada, e a fronteira move-se para a direita
Algoritmos de ordenação
compare adjacent, swap if needed
Step through a bubble sort: each pass floats the largest value to the end.
Bubble sort works by:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Each pass swaps adjacent pairs, "bubbling" the largest element to the end.
The average/worst-case time complexity of bubble sort is:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit.
Exemplo resolvido: rastreie uma passagem
- Rastreie a primeira passagem de uma ordenação por bolhas em 5, 3, 8, 1.
- Compare 5 e 3: fora de ordem, troque, resultando em 3, 5, 8, 1. Compare 5 e 8: em ordem, não troque. Compare 8 e 1: troque, resultando em 3, 5, 1, 8.
- Após uma passagem, o maior valor, 8, está em sua posição final, e uma comparação a menos por passagem pode ser pulada a partir de agora.
- Agora rastreie o terceiro passo da ordenação por inserção em 3, 5, 8, 1. A chave é 1. Mova 8, 5 e 3 cada um um lugar para a direita, depois insira 1 na frente: 1, 3, 5, 8. Mostre o array após cada passo; é aí que estão os pontos.
Insertion sort builds the sorted result by:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
It grows a sorted prefix on the left, shifting larger elements right to drop each key into place.
How does insertion sort place each new element?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps.
Desempenho
| bolhas | inserção | |
|---|---|---|
| melhor caso | $O(n)$, uma passagem sem trocas | $O(n)$, já ordenada, sem deslocamentos |
| média e pior | $O(n^2)$ | $O(n^2)$ |
| memória extra | $O(1)$, in place原地 | $O(1)$, in place |
| estável | sim | sim, stable稳定 |
- In place significa que precisa apenas de uma quantidade constante de memória extra, ordenando dentro do próprio array. Stable significa que dois valores iguais mantêm sua ordem relativa original, o que importa quando uma lista já foi ordenada por outro campo.
- Ambos alcançam $O(n)$ em dados já ordenados, mas apenas se o bubble sort tiver a bandeira
swapped. Sem ela, ele sempre executa todas as passagens.
After the first pass of a bubble sort on 5, 3, 8, 1, what is the array? Write the four numbers separated by commas.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
5 and 3 swap, 5 and 8 do not, 8 and 1 swap. The largest value has reached the end, so the next pass can be one comparison shorter.
Exemplo resolvido: qual ordenação e por quê
- Uma lista de 200,000 registros deve ser ordenada do zero. Nem: ambos são $O(n^2)$, portanto uma mesclagem ou quick sort em $O(n \log n)$ é necessária. Diga isso em vez de escolher o menos pior.
- Uma lista ordenada de 10,000 ganha 5 novos registros no final e deve ser reordenada. Ordenação por inserção: os dados estão quase ordenados, então cada nova chave se desloca apenas uma curta distância e se aproxima de $O(n)$.
- Um exemplo didático deve ser rastreado à mão em papel. Bubble sort: é o mais simples de seguir, que é seu único uso restante.
- Justifique pelo estado dos dados e pelo tamanho, não por uma preferência geral.
Match each sorting idea to what it means.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order.
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
On nearly-sorted data each new item is already almost in place — which is why insertion sort beats fancier sorts on small inputs.
Which are true of both bubble sort and insertion sort? Select todos that apply.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
On a large unsorted list an O(n log n) sort wins decisively. Saying so is the right answer, not choosing the least bad of the two.
Por que uma passagem não é a história toda
- Ambas as ordenações fazem passagens repetidas, e o exame as distingue pelo que uma passagem alcança e por quando elas paramem.
- Uma passagem de bubble sort compara pares adjacentes e as troca, então uma passagem leva o maior item restante para sua posição final. A ordenação inteira é $n - 1$ passagens.
- Uma passagem de insertion sort pega o próximo item e o move de volta para a parte já ordenada, então após $k$ passagens os primeiros $k$ itens estão ordenados entre si, mas ainda não em posição final.
- O bubble sort pode ser melhorado com uma bandeira: se uma passagem não faz nenhuma troca, a lista já está ordenada e o algoritmo para. Em dados quase ordenados, isso o transforma em uma única passagem.
- Sem a bandeira, ambas são $n^2$ no pior caso, que é por que qualquer uma é uma má escolha para um arquivo grande e por que o exame pergunta sobre pequenos.
A sorted list of 10,000 records gains 5 new records at the end. Which sort suits re-sorting it?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason.
Match each sort to what one pass achieves.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
That difference is what a trace question is really testing. A bubble-sort flag also lets it stop early on nearly-sorted data, which insertion sort handles well anyway.
Marcas que escapam
- O bubble sort compara pares adjacentes. Uma resposta que compara um elemento com todos os outros está descrevendo um algoritmo diferente.
- O loop interno encurta a cada passagem, porque o final do array já está definido. Diga o porquê.
- A ordenação por inserção desloca elementos para a direita para abrir espaço; ela não troca repetidamente. A distinção é o ponto do algoritmo.
- Ambas são $O(n^2)$ na média e no pior caso, e $O(n)$ no melhor. Dê o caso com a ordem.
Entendeu?
- bubble sort: passagens repetidas comparando pares adjacentes e trocando, o maior borbulhando para o final, loop interno encurtando a cada passagem, com uma bandeira
swappedpara saída antecipada - insertion sort: cresce uma seção ordenada na frente, mantendo cada chave de lado, deslocando elementos maiores para a direita e inserindo a chave no espaço aberto
- ambas são $O(n^2)$ na média e no pior, $O(n)$ no melhor, in place e stable
- a insertion sort genuinamente vence em listas pequenas ou quase ordenadas; para uma lista grande desordenada nenhuma delas é a resposta certa