Sorting algorithms
Introducido| English | Significado |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | ordenamiento burbuja |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | ordenamiento por inserción |
| in place/ɪn pleɪs/ | in situ |
| stable/ˈsteɪbl/ | estable |
La ordenación que es lenta a propósito
- Toda biblioteca seria ordena con un algoritmo que ningún examen le pide escribir. Bubble sort e insertion sort son ambos $O(n^2)$, y ambos son superados por cualquier ordenación decente en una lista grande.
- Están en el temario de todas formas, y por una buena razón: son lo suficientemente cortos para rastrearlos a mano, y rastrear uno es cómo aprendes lo que realmente hace una ordenación a un array.
- También hay un caso real para insertion sort. En una lista que es pequeña, o ya casi ordenada, es genuinamente lo más rápido que existe, y las bibliotecas reales cambian a él exactamente para esos casos.
- Esta lección es bubble sort 冒泡排序 e insertion sort 插入排序: los algoritmos, su comportamiento, y dónde gana cada uno.
Ordenamiento burbuja
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 pasada compara pares adyacentes e intercambia cualquiera que esté fuera de orden, por lo que el valor restante más grande "burbujea" hasta el final.
- Después de la pasada $k$ los últimos $k$ elementos están definitivos, por eso el bucle interno se detiene en $n - \text{pass}$.
- La bandera
swappedpermite detenerse antes: si una pasada completa no realiza ningún intercambio, la lista está ordenada.
Ordenamiento por inserción
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
- Construye una sección ordenada al principio, creciendo de uno en uno. Cada nuevo elemento se aparta como
key, los elementos más grandes se desplazan a la derecha para abrir un hueco, y la clave se coloca allí. - Así es como la mayoría de la gente ordena una mano de cartas de jugar, que es la analogía que espera el examen.

La izquierda está ordenada, la derecha está intacta, y el límite se mueve a la derecha
Algoritmos de ordenación
compare adjacent, swap if needed
Step through a bubble sort: each pass floats the largest value to the end.
Bubble sort works by:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Each pass swaps adjacent pairs, "bubbling" the largest element to the end.
The average/worst-case time complexity of bubble sort is:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit.
Ejemplo resuelto: rastrear una pasada
- Rastree la primera pasada de un bubble sort en 5, 3, 8, 1.
- Compare 5 y 3: fuera de orden, intercambie, dando 3, 5, 8, 1. Compare 5 y 8: en orden, sin intercambio. Compare 8 y 1: intercambie, dando 3, 5, 1, 8.
- Después de una pasada el valor más grande, 8, está en su posición final, y se puede omitir una comparación más por pasada de ahora en adelante.
- Ahora rastree el tercer paso de insertion sort en 3, 5, 8, 1. La clave es 1. Desplace 8, 5 y 3 cada uno un lugar a la derecha, luego coloque 1 al frente: 1, 3, 5, 8. Muestre el array después de cada paso; ahí están las marcas.
Insertion sort builds the sorted result by:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps.
Rendimiento
| bubble | insertion | |
|---|---|---|
| mejor caso | $O(n)$, una pasada sin intercambios | $O(n)$, ya ordenado, sin desplazamientos |
| promedio y peor caso | $O(n^2)$ | $O(n^2)$ |
| memoria extra | $O(1)$, in place 原地 | $O(1)$, in place |
| estable | sí | sí, stable 稳定 |
- In place significa que solo necesita una cantidad constante de memoria extra, ordenando dentro del propio array. Stable significa que dos valores iguales mantienen su orden relativo original, lo cual importa cuando una lista ya ha sido ordenada por otro campo.
- Ambos alcanzan $O(n)$ en datos ya ordenados, pero solo si bubble sort tiene la bandera
swapped. Sin ella, siempre realiza todas las pasadas.
After the first pass of a bubble sort on 5, 3, 8, 1, what is the array? Write the four numbers separated by commas.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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.
Ejemplo resuelto: qué ordenación, y por qué
- Una lista de 200,000 registros debe ordenarse desde cero. Ni uno ni otro: ambos son $O(n^2)$, por lo que se necesita una fusión o un ordenamiento rápido en $O(n \log n)$. Dicho esto, en lugar de elegir el menos malo.
- Una lista ordenada de 10,000 obtiene 5 nuevos registros al final y debe ordenarse nuevamente. Ordenamiento por inserción: los datos están casi ordenados, por lo que cada nueva clave se desplaza solo una corta distancia y se aproxima a $O(n)$.
- Un ejemplo educativo debe rastrearse a mano en papel. Bubble sort: es el más simple de seguir, que es su uso real restante.
- Justifique desde el estado de los datos y el tamaño, no desde una preferencia general.
Match each sorting idea to what it means.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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 qué una pasada no es toda la historia
- Ambas ordenaciones realizan pasadas repetidas, y el examen las distingue por lo que logra una pasada y por cuándo se detienen.
- Una pasada de bubble sort compara pares adyacentes y los intercambia, por lo que una pasada lleva el artículo restante más grande a su lugar final. La ordenación completa son $n - 1$ pasadas.
- Una pasada de insertion sort toma el artículo siguiente y lo mueve hacia atrás en la parte ya ordenada, por lo que después de $k$ pasadas los primeros $k$ artículos están ordenados entre sí pero aún no en posición final.
- Bubble sort puede mejorarse con una bandera: si una pasada no realiza intercambios, la lista ya está ordenada y el algoritmo se detiene. En datos casi ordenados eso lo convierte en una pasada.
- Sin la bandera, ambas son $n^2$ en el peor caso, por lo que cualquiera es una mala elección para un archivo grande y por eso el examen pregunta sobre los pequeños.
A sorted list of 10,000 records gains 5 new records at the end. Which sort suits re-sorting it?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
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.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
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.
Puntos que se pierden fácilmente
- Bubble sort compara pares adyacentes. Una respuesta que compara un elemento con todos los demás describe un algoritmo diferente.
- El bucle interno se acorta cada pasada, porque el final del array ya es definitivo. Diga por qué.
- Insertion sort desplaza elementos a la derecha para abrir un hueco; no intercambia repetidamente. La distinción es el punto del algoritmo.
- Ambas son $O(n^2)$ en promedio y en el peor caso, y $O(n)$ en el mejor caso. Dé el caso con el orden.
Lo has entendido
- bubble sort: pasadas repetidas comparando pares adyacentes e intercambiándolos, el mayor burbujeando al final, el bucle interno acortándose cada pasada, con una bandera
swappedpara salida anticipada - insertion sort: crecer una sección ordenada al principio, manteniendo cada clave aparte, desplazando elementos más grandes a la derecha y dejando caer la clave en el hueco
- ambas son $O(n^2)$ promedio y peor caso, $O(n)$ mejor caso, in place y stable
- insertion sort gana genuinamente en listas pequeñas o casi ordenadas; para una lista grande no ordenada ninguna es la respuesta correcta