Algoritmos de Ordenamiento
Introducido| English | Significado |
|---|---|
| Sorting/ˈsɔːtɪŋ/ | Ordenación |
| selection sort/sɪˈlekʃn sɔːt/ | ordenación por selección |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | ordenación por inserción |
| in place/ɪn pleɪs/ | in situ |
Ordenando elementos
- Ordenar reorganiza los elementos en orden (de menor a mayor, por ejemplo).
- El curso AP cubre dos métodos de ordenación 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.
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.

Ordenación por inserción, desplazando cada clave a su lugar paso a paso
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.
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.
- Ordena en el sitio — no se necesita una segunda matriz.
- El examen te pide rastrear su ejecución, no solo nombrarlos.
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.
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.
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.
Paso a paso en un ordenamiento
Cada pasada coloca un elemento más en su posición correcta.
El selection sort funciona mediante...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
El selection sort selecciona el mínimo y lo intercambia hacia adelante.
El insertion sort funciona mediante...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
El insertion sort inserta cada elemento en su lugar ordenado.
En el peor caso, ambos algoritmos realizan aproximadamente...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Los bucles anidados dan O(n²).
Tanto el selection como el insertion sort funcionan in situ (sin una segunda matriz).
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Reorganizan la misma matriz.
Ordena las pasadas del selection sort sobre [3, 1, 2].
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
La parte frontal crece ordenada, un elemento por pasada.
Ordenar primero es útil porque permite luego usar...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
La búsqueda binaria necesita datos ordenados.