Sorting algorithms · Algoritmos de ordenación
| English | Español |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | bubble sort |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | insertion sort |
| in place/ɪn pleɪs/ | in situ |
| stable/ˈsteɪbl/ | estable |
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.
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.
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.
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.
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
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
Sorting algorithms · Algoritmos de ordenación
compare adjacent, swap if needed · comparar adyacentes, intercambiar si es necesario
Step through a bubble sort: each pass floats the largest value to the end. · Recorrer paso a paso un bubble sort: cada pasada flota el valor más grande hacia el final.
Bubble sort works by: · El bubble sort funciona mediante:
Each pass swaps adjacent pairs, "bubbling" the largest element to the end. · Cada pasada intercambia pares adyacentes, "subiendo" el elemento más grande al final.
The average/worst-case time complexity of bubble sort is: · La complejidad temporal promedio/casos peores del bubble sort es:
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit. · Dos bucles anidados sobre n elementos dan O(n²); el mejor caso (ya ordenado) es O(n) con salida anticipada.
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.
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: · El insertion sort construye el resultado ordenado mediante:
It grows a sorted prefix on the left, shifting larger elements right to drop each key into place. · Crece un prefijo ordenado a la izquierda, desplazando elementos mayores a la derecha para colocar cada clave en su sitio.
How does insertion sort place each new element? · ¿Cómo coloca el insertion sort cada nuevo elemento?
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps. · Guardar la clave a un lado y desplazar es lo que lo distingue de los intercambios adyacentes repetidos del bubble sort.
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.
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. · Después de la primera pasada de un bubble sort sobre 5, 3, 8, 1, ¿cuál es el array? Escribe los cuatro números separados por comas.
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 y 3 se intercambian, 5 y 8 no, 8 y 1 se intercambian. El valor más grande ha llegado al final, así que la siguiente pasada puede ser una comparación más corta.
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.
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. · Empareja cada idea de ordenación con lo que significa.
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order. · El bubble sort intercambia vecinos, el insertion sort crece un prefijo ordenado; ambos son O(n²) en el peor caso; la estabilidad se refiere al orden de claves iguales.
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted. · El insertion sort se acerca a O(n) en arrays pequeños o casi ordenados, porque pocos elementos necesitan ser desplazados.
On nearly-sorted data each new item is already almost in place — which is why insertion sort beats fancier sorts on small inputs. · En datos casi ordenados, cada nuevo ítem ya está casi en su sitio, por eso el insertion sort supera a algoritmos más sofisticados en entradas pequeñas.
Which are true of both bubble sort and insertion sort? Select all · todos that apply. · ¿Qué afirmaciones son ciertas tanto para el bubble sort como para el insertion sort? Selecciona todas las que correspondan.
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. · En una lista grande desordenada, una ordenación O(n log n) gana decisivamente. Decir lo contrario es la respuesta correcta, no elegir la menos mala de las dos.
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 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? · Una lista ordenada de 10.000 registros recibe 5 nuevos registros al final. ¿Qué ordenación conviene para reordenarla?
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason. · Los datos casi ordenados son exactamente el mejor caso del insertion sort, acercándose a O(n). Las bibliotecas reales cambian a este algoritmo por esta razón.
Match each sort to what one pass achieves. · Empareja cada ordenación con lo que logra una sola pasada.
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. · Esa diferencia es lo que realmente prueba una pregunta de trazo. Una bandera del bubble sort también permite detenerse anticipadamente en datos casi ordenados, cosa que el insertion sort maneja bien de todos modos.
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.
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.
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
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