Sorting Algorithms · Algoritmos de Ordenamiento
| English | Español |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | Ordenamiento |
| selection sort/sɪˈlekʃn sɔːt/ | ordenamiento por selección |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | insertion sort |
| in place/ɪn pleɪs/ | in situ |
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.
Ordenando elementos
- Ordenamiento 排序 reorganiza los elementos en un orden (de menor a mayor, por ejemplo).
- El curso AP cubre dos tipos de ordenamiento simples: ordenamiento por selección 选择排序 y ordenamiento por inserción 插入排序.
- Ambos utilizan bucles anidados e intercambian o desplazan los elementos a su posición correcta.
- Realizar el ordenamiento primero es lo que permite utilizar una búsqueda binaria rápida posteriormente.
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.
Ordenamiento por selección
- Encuentra el elemento restante más pequeño e intercámbialo hacia el frente.
- Luego encuentra el más pequeño de los restantes, intercámbialo en la siguiente posición, y así sucesivamente.
- La parte frontal del arreglo crece ordenada; la parte trasera se encoge siendo desordenada.
- Un intercambio por pasada — pero sigue escaneando el resto en cada pasada.
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.
Ordenamiento por inserción
- Toma el siguiente elemento y desplázalo hacia atrás a su lugar correcto entre la parte ya ordenada del frente.
- Similar a ordenar una mano de cartas: coloca cada nueva carta donde corresponda.
- La región ordenada crece en uno por pasada.
- Es rápido cuando los datos están ya casi 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.
Cuánto trabajo implica
- Ambos algoritmos usan bucles anidados, por lo que realizan aproximadamente
n²comparaciones en el peor caso. - Esto es aceptable para arreglos pequeños, pero lento para muy grandes.
- Ordenan in situ 原地 — no necesitan un segundo arreglo.
- El examen te pide rastrear su ejecución, no solo nombrarlos.
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.
El ordenamiento por selección INTERCAMBIA el elemento restante más pequeño al frente; el ordenamiento por inserción DESPLAZA cada nuevo elemento hacia atrás en la parte ordenada — no los confundas. Ambos son algoritmos de bucle anidado O(n²) y ambos ordenan in situ. Rastrea su ejecución paso a paso (el examen AP pide el estado del arreglo después de cada pasada) en lugar de memorizar sus nombres.
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.
Ordenamiento por selección sobre [3, 1, 2]:
- Pasada 1: el más pequeño es
1; intercambio al frente →[1, 3, 2]. - Pasada 2: el más pequeño de
[3, 2]es2; intercambio →[1, 2, 3]. - Ordenado — la parte frontal creció un elemento por pasada.
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 significa dar orden a los elementos. El ordenamiento por selección intercambia repetidamente el elemento restante más pequeño al frente; el ordenamiento por inserción desplaza cada nuevo elemento hacia atrás en la parte ordenada. Ambos son algoritmos de bucle anidado, in situ y O(n²). El ordenamiento habilita una búsqueda binaria rápida posteriormente.
Stepping through a sort · Paso a paso en un ordenamiento
Each pass places one more element in order. · Cada pasada coloca un elemento más en su posición correcta.
Selection sort works by... · El selection sort funciona mediante...
Selection sort selects the minimum and swaps it forward. · El selection sort selecciona el mínimo y lo intercambia hacia adelante.
Insertion sort works by... · El insertion sort funciona mediante...
Insertion sort inserts each element into its sorted place. · El insertion sort inserta cada elemento en su lugar ordenado.
In the worst case, both sorts do about... · En el peor caso, ambos algoritmos realizan aproximadamente...
Nested loops give O(n²). · Los bucles anidados dan O(n²).
Both selection and insertion sort work in place (no second array). · Tanto el selection como el insertion sort funcionan in situ (sin una segunda matriz).
They rearrange the same array. · Reorganizan la misma matriz.
Order the passes of selection sort on [3, 1, 2]. · Ordena las pasadas del selection sort sobre [3, 1, 2].
Front grows sorted, one element per pass. · La parte frontal crece ordenada, un elemento por pasada.
Sorting first is useful because it lets you later use... · Ordenar primero es útil porque permite luego usar...
Binary search needs sorted data. · La búsqueda binaria necesita datos ordenados.