Sorting algorithms · Algoritmos de ordenação
| English | Português |
|---|---|
| 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/ | in place |
| stable/ˈsteɪbl/ | estável |
The sort that is slow on purpose
- Every serious library sorts with an algorithm no exam asks you to write. Bubble sort and insertion sort are both $O(n^2)$, and both are beaten by any decent sort on a large list.
- They are on the syllabus anyway, and for a good reason: they are short enough to trace by hand, and tracing one is how you learn what a sort actually does to an array.
- There is also a real case for insertion sort. On a list that is small, or already nearly sorted, it is genuinely the fastest thing there is, and real libraries switch to it for exactly those cases.
- This lesson is bubble sort 冒泡排序 and insertion sort 插入排序: the algorithms, their behaviour, and where each one wins.
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.
Bubble sort
- Each pass compares adjacent pairs and swaps any that are out of order, so the largest remaining value "bubbles" to the end.
- After pass $k$ the last $k$ elements are final, which is why the inner loop stops at $n - \text{pass}$.
- The
swappedflag lets it stop early: if a whole pass makes no swap, the list is sorted.
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
- It builds a sorted section at the front, growing by one each time. Each new element is held aside as
key, larger elements are shifted right to open a gap, and the key is dropped in. - This is how most people sort a hand of playing cards, which is the analogy the exam expects.
The left is sorted, the right is untouched, and the boundary moves right
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
Sorting algorithms · Algoritmos de ordenação
compare adjacent, swap if needed · comparar adjacentes, trocar se necessário
Step through a bubble sort: each pass floats the largest value to the end. · Passo a passo de uma ordenação por bolha: cada passagem faz flutuar o maior valor para o final.
Bubble sort works by: · A ordenação por bolha funciona através de:
Each pass swaps adjacent pairs, "bubbling" the largest element to the end. · Cada passagem troca pares adjacentes, "bolheando" o maior elemento para o final.
The average/worst-case time complexity of bubble sort is: · A complexidade de tempo média/pior caso da ordenação por bolha é:
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit. · Dois loops aninhados sobre n elementos dão O(n²); o melhor caso (já ordenado) é O(n) com saída antecipada.
Worked example: trace one pass
- Trace the first pass of a bubble sort on 5, 3, 8, 1.
- Compare 5 and 3: out of order, swap, giving 3, 5, 8, 1. Compare 5 and 8: in order, no swap. Compare 8 and 1: swap, giving 3, 5, 1, 8.
- After one pass the largest value, 8, is in its final position, and one more comparison per pass can be skipped from now on.
- Now trace insertion sort's third step on 3, 5, 8, 1. The key is 1. Shift 8, 5 and 3 each one place right, then place 1 at the front: 1, 3, 5, 8. Show the array after every step; that is where the marks are.
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: · A ordenação por inserção constrói o resultado ordenado através de:
It grows a sorted prefix on the left, shifting larger elements right to drop each key into place. · Ela cresce um prefixo ordenado à esquerda, deslocando elementos maiores para a direita para encaixar cada chave no lugar.
How does insertion sort place each new element? · Como a ordenação por inserção posiciona cada novo elemento?
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps. · Segurar a chave de lado e deslocar é o que a diferencia das trocas adjacentes repetidas da ordenação por bolha.
Performance
| bubble | insertion | |
|---|---|---|
| best case | $O(n)$, one pass with no swaps | $O(n)$, already sorted, no shifts |
| average and worst | $O(n^2)$ | $O(n^2)$ |
| extra memory | $O(1)$, in place 原地 | $O(1)$, in place |
| stable | yes | yes, stable 稳定 |
- In place means it needs only a constant amount of extra memory, sorting within the array itself. Stable means two equal values keep their original relative order, which matters when a list has already been sorted by another field.
- Both reach $O(n)$ on already-sorted data, but only if bubble sort has the
swappedflag. Without it, it always performs every pass.
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. · Após a primeira passagem de uma ordenação por bolha em 5, 3, 8, 1, qual é o array? Escreva os quatro números separados por vírgulas.
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. · 5 e 3 trocam, 5 e 8 não trocam, 8 e 1 trocam. O maior valor atingiu o final, então a próxima passagem pode ser uma comparação mais curta.
Worked example: which sort, and why
- A list of 200,000 records must be sorted from scratch. Neither: both are $O(n^2)$, so a merge or quick sort at $O(n \log n)$ is needed. Say so rather than choosing the least bad.
- A sorted list of 10,000 gains 5 new records at the end and must be sorted again. Insertion sort: the data is nearly sorted, so each new key shifts only a short distance and it approaches $O(n)$.
- A teaching example must be traced by hand on paper. Bubble sort: it is the simplest to follow, which is its real remaining use.
- Justify from the state of the data and the size, not from a general preference.
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. · Combine cada ideia de ordenação com o que ela significa.
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order. · A bolha troca vizinhos, a inserção cresce um prefixo ordenado; ambas têm pior caso O(n²); estabilidade trata-se da ordem de chaves iguais.
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted. · A ordenação por inserção roda perto de O(n) em arrays pequenos ou quase ordenados, pois poucos elementos precisam ser deslocados.
On nearly-sorted data each new item is already almost in place — which is why insertion sort beats fancier sorts on small inputs. · Em dados quase ordenados, cada novo item já está quase no lugar — é por isso que a ordenação por inserção supera ordenações mais sofisticadas em entradas pequenas.
Which are true of both bubble sort and insertion sort? Select all · todos that apply. · Quais são verdadeiras tanto para a ordenação por bolha quanto para a ordenação por inserção? Selecione todas as que se aplicam.
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. · Em uma lista grande desordenada, uma ordenação O(n log n) vence decisivamente. Dizer isso é a resposta certa, não escolher o menos ruim dos dois.
Why one pass is not the whole story
- Both sorts do repeated passes, and the exam distinguishes them by what one pass achieves and by when they stop.
- A bubble sort pass compares adjacent pairs and swaps them, so one pass carries the largest remaining item to its final place. The whole sort is $n - 1$ passes.
- An insertion sort pass takes the next item and moves it back into the already-sorted part, so after $k$ passes the first $k$ items are sorted among themselves but not yet in final position.
- Bubble sort can be improved with a flag: if a pass makes no swaps, the list is already sorted and the algorithm stops. On nearly-sorted data that turns it into one pass.
- Without the flag, both are $n^2$ in the worst case, which is why either is a poor choice for a large file and why the exam asks about small ones.
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? · Uma lista ordenada de 10,000 registros ganha 5 novos registros no final. Qual algoritmo de ordenação é mais adequado para reordená-la?
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason. · Dados quase ordenados são exatamente o melhor caso da ordenação por inserção, aproximando-se de O(n). Bibliotecas reais mudam para ela por esse motivo.
Match each sort to what one pass achieves. · Combine cada ordenação com o que uma passagem alcança.
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. · Essa diferença é o que uma questão de traço realmente testa. Uma flag de ordenação por bolha também permite parar cedo em dados quase ordenados, algo que a ordenação por inserção lida bem de qualquer forma.
Marks that slip away
- Bubble sort compares adjacent pairs. An answer that compares an element with all the others is describing a different algorithm.
- The inner loop shortens each pass, because the end of the array is already final. Say why.
- Insertion sort shifts elements right to open a gap; it does not swap repeatedly. The distinction is the point of the algorithm.
- Both are $O(n^2)$ on average and at worst, and $O(n)$ at best. Give the case with the order.
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.
You've got it
- bubble sort: repeated passes comparing adjacent pairs and swapping, largest bubbling to the end, inner loop shortening each pass, with a
swappedflag for early exit - insertion sort: grow a sorted section at the front, holding each key aside, shifting larger elements right and dropping the key into the gap
- both are $O(n^2)$ average and worst, $O(n)$ best, in place and stable
- insertion sort genuinely wins on small or nearly sorted lists; for a large unsorted list neither is the right answer
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