Recursive Searching and Sorting
Introducido| English | Significado |
|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | dividir y vencerás |
| merge sort/mɜːdʒ sɔːt/ | ordenamiento por fusión |
| merge/mɜːdʒ/ | fusión |
Recursión meets search and sort
- La misma idea de divide y vencerás (divide-and-conquer) impulsa la búsqueda binaria recursiva y el ordenamiento por fusión recursivo.
- Divide el problema a la mitad, resuelve las mitades y combínalas.
- La búsqueda binaria recursiva busca en una mitad llamándose a sí misma sobre ella.
- El ordenamiento por fusión ordena cada mitad y luego fusiona las mitades ordenadas juntas.
Búsqueda binaria recursiva
- Caso base: un rango vacío significa que el objetivo no se encontró.
- Mira el centro. Si es el objetivo, devuelve su índice.
- Si el objetivo es menor, recurre sobre la mitad izquierda; si es mayor, la mitad derecha.
- Cada llamada reduce el rango a la mitad — el mismo
O(log n), escrito de forma recursiva.
Ordenamiento por fusión
- Divide el arreglo en dos mitades; ordena cada mitad recursivamente.
- Caso base: un arreglo de 0 o 1 elemento ya está ordenado.
- Fusiona: recorre ambas mitades ordenadas, tomando siempre el elemento más pequeño del frente.
- Mucho más rápido que los ordenamientos
n²— aproximadamenten log nde trabajo.
Por qué divide y vencerás gana
- Reducir a la mitad el problema en cada paso da el factor
log n. - El
n log ndel ordenamiento por fusión supera aln²de los algoritmos de selección e inserción en arreglos grandes. - El caso base (vacío o un solo elemento) detiene cada rama.
- Mismo patrón que toda recursión: dividir hacia abajo, combinar hacia arriba.
La búsqueda binaria recursiva recurre sobre UNA mitad (el objetivo solo está en un lado); el ordenamiento por fusión recurre sobre AMBAS mitades y luego las fusiona. Ambos necesitan un caso base —un rango vacío significa "no encontrado" para la búsqueda; un arreglo de 0 o 1 elemento ya está ordenado para el ordenamiento por fusión. Es divide y vencerás lo que los hace rápidos (O(log n) y O(n log n)).
Ordenando por fusión [3, 1, 2, 4]:
- Dividir en
[3, 1]y[2, 4]; ordenar cada uno →[1, 3]y[2, 4]. - Fusionar: tomar 1, luego 2, luego 3, luego 4 →
[1, 2, 3, 4]. - Cada fusión selecciona el elemento más pequeño del frente en turno.
La búsqueda binaria recursiva recurre sobre una mitad (caso base: rango vacío = no encontrado) para una búsqueda O(log n). El ordenamiento por fusión recurre sobre ambas mitades y las fusiona (caso base: 0 o 1 elemento) para un ordenamiento O(n log n). Ambos son divide y vencerás: dividen hacia abajo, combinan hacia arriba — mucho más rápidos que n².
Merge sort splits into halves, then merges up
Single elements are sorted (base case); merges combine them upward.
Recursive binary search recurses on...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
The target is only on one side of the middle.
Merge sort recurses on...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Sort each half, then merge the two sorted halves.
The base case for merge sort is an array of...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
One (or zero) element needs no sorting.
Merge sort's running time is about...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
log n levels of splitting, n work per level.
Both recursive binary search and merge sort are divide-and-conquer algorithms.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Both split the problem in half and recurse.
Order the merge step for halves [1,3] and [2,4].
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Always take the smaller front element: 1, 2, 3, 4.