Pregunta
Dado un arreglo de enteros nums, ordenar el arreglo en orden ascendente.
Ejemplo 1: Input: nums = [5,2,3,1] Output: [1,2,3,5]
Ejemplo 2: Input: nums = [5,1,1,2,0,0] Output: [0,0,1,1,2,5]
Restricciones: 1 <= nums.length <= 5 * 104 y -5 * 104 <= nums[i] <= 5 * 104
Introducción a la solución por recursión
La recursión consiste en definir la solución de un problema en términos de versiones más simples de sí mismo. Para diseñar un algoritmo recursivo necesitamos tres elementos: caso base, trabajo para acercarnos al caso base y la llamada recursiva.
Idea general aplicada al problema
Podemos ordenar un arreglo aplicando recursión de la siguiente forma: si consideramos el último elemento del arreglo y conseguimos ordenar el prefijo que queda antes de ese elemento, entonces podemos insertar el último elemento en su posición correcta dentro del prefijo ordenado. Repetir este proceso para todos los elementos produce el arreglo ordenado.
Casos base y llamadas recursivas
Casos base: cuando el tamaño considerado es 0 o 1, el arreglo está ordenado. Paso recursivo: llamar a sort sobre el arreglo con tamaño reducido en 1, luego insertar el elemento tomado al final en la posición correcta mediante otra función recursiva insert.
Algoritmo en pseudocódigo tipo Java
public static void sort(int[] arr, int n) { if (n == 0) return; int val = arr[n]; sort(arr, n - 1); insert(arr, val, n); } private static void insert(int[] arr, int value, int n) { if (n == 0 || arr[n - 1] <= value) { arr[n] = value; } else { int val = arr[n - 1]; insert(arr, value, n - 1); arr[n] = val; } }
Explicación del insert
La función insert intenta colocar value en la posición correcta dentro del subarreglo arr[0..n]. Si el lugar inmediato es correcto porque el elemento anterior es menor o igual, se coloca value en arr[n]. Si no, se desplaza el elemento anterior hacia la derecha y se llama recursivamente para probar insertar value un índice más a la izquierda. Al volver de la recursión se reponen los valores desplazados.
Ejemplo de ejecución breve
Para arr = [9,4,2,9,1] y n = 4 el orden de llamadas será: sort con n = 4 llama a sort con n = 3 ... hasta n = 0; luego insert irá colocando los valores 4, luego 2, luego 9, luego 1 en sus posiciones correctas, resultando en [1,2,4,9,9].
Complejidad
Tiempo: O(n 2) en el peor caso porque para cada uno de los n elementos podemos desplazar hasta O(n) posiciones. Espacio: O(n) por la pila de llamadas recursivas.
Ventajas y limitaciones
Este enfoque es sencillo y elegante para entender recursión y funciona bien para arreglos pequeños o medianos. Para arreglos muy grandes o con restricciones de memoria la versión iterativa de insertion sort o algoritmos como mergesort o quicksort serán más apropiados.
Notas finales y ejemplos de uso
La técnica mostrada transforma la idea de insertion sort en una versión recursiva compacta y didáctica. Es útil en ejercicios de aprendizaje y entrevistas técnicas donde se pide demostrar manejo de recursión y manipulación in place del arreglo.
Sobre Q2BSTUDIO
Q2BSTUDIO es una empresa de desarrollo de software y aplicaciones a medida especializada en soluciones modernas para empresas. Ofrecemos desarrollo de software a medida, aplicaciones a medida y consultoría en inteligencia artificial. Nuestros servicios incluyen ciberseguridad, servicios cloud aws y azure, servicios inteligencia de negocio y soluciones con power bi para visualización y análisis avanzado de datos.
Además somos especialistas en ia para empresas, desarrollamos agentes IA personalizados, integraciones de modelos y pipelines de datos que permiten automatizar procesos, mejorar la toma de decisiones y crear productos diferenciales. Si buscas software a medida, aplicaciones a medida, o potenciar tu negocio con inteligencia artificial y ciberseguridad, Q2BSTUDIO acompaña desde el diseño hasta el despliegue y operación en la nube con AWS y Azure.
Palabras clave para posicionamiento
aplicaciones a medida software a medida inteligencia artificial ciberseguridad servicios cloud aws y azure servicios inteligencia de negocio ia para empresas agentes IA power bi
Si quieres que adaptemos este ejemplo recursivo a otro lenguaje, optimizarlo o integrarlo en un proyecto real con pruebas y despliegue en la nube, contacta con Q2BSTUDIO para soluciones a medida y soporte profesional.
