let swapFun = (arrToSwap, indexFir, indexSec) => { let temp = arrToSwap[indexFir] arrToSwap[indexFir] = arrToSwap[indexSec] arrToSwap[indexSec] = temp } let insertionSort = (arr, n = 0) => { if (n === arr.length) { return arr } for (let i = 1; i < arr.length; i++) { while (arr[i - 1] > arr[i]) { swapFun(arr, i - 1, i) } } insertionSort(arr, n + 1) return arr } console.log(insertionSort([5, 4, 33, 2, 8]))En realidad es Bubble Sort , pero es una mala implementación de Bubble Sort.
Si notas el bucle for:
for (let i = 1; i < arr.length; i++) { while (arr[i - 1] > arr[i]) { swapFun(arr, i - 1, i) } }básicamente itera la matriz, comenzando desde el índice 1, hasta el final de la matriz, y para cada elemento, compara el elemento con el elemento anterior. La comparación se realiza en el ciclo while, pero en realidad no es un ciclo (simplemente ejecuta el cuerpo si el elemento en el índice i-1 es más grande que el elemento en el índice 1). Se puede reemplazar con una declaración if:
for (let i = 1; i < arr.length; i++) { if (arr[i - 1] > arr[i]) { swapFun(arr, i - 1, i) } }El bucle for se ejecuta un total de n-1 veces , porque n=0 al principio y se incrementa cada vez que se llama recursivamente a la función, hasta que alcanza n=longitud de matriz (esta vez el bucle for no se ejecutará). el cuerpo del bucle for se ejecuta array.length-1 veces (4 veces en su ejemplo).
El mayor problema con esta implementación es el uso de Recursion , que usará más espacio (porque Recursion usa una pila). Tampoco está optimizado con respecto al tiempo. Incluso si la matriz ya estuviera ordenada , el bucle for se ejecutaría N-1 veces , y su cuerpo también se ejecutaría N-1 veces . Lo que significa que incluso en el mejor de los casos (la matriz ya está ordenada), este tipo de burbuja tendría una complejidad de tiempo O (n ^ 2) , cuando de hecho puede ser O (n).
La versión optimizada de Bubble Sort:
const sort = array => { let isSorted; for (let i=0; i < array.length; i++) { isSorted = true; for (let j=1; j < array.length - i; j++) if ( array[j] < array[j-1]) { swap(array, j, j-1); isSorted = false; } if (isSorted) return; } } const swap = (array, index1, index2) => { let temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } const array = [5, 4, 33, 2, 8] sort(array); console.log(array);La variable "isSorted", realiza un seguimiento si la matriz está ordenada o no. Si no se realizaron intercambios, significa que la matriz está ordenada y puedo detener la ejecución de la función. También tenga en cuenta que en el ciclo interno: for (let j=1; j < array.length - i; j++), no verificamos los elementos en la "parte ordenada" (cada vez que se ejecuta el ciclo interno, un elemento va a su índice "final" en la matriz y no necesitamos hacer ninguna comparación con estos elementos).
¡Espero que esto haya ayudado! Por favor, pregunte si no expliqué algo correctamente.