En el post anterior hablábamos sobre cómo era posible saber si un array estaba ordenado y veíamos una forma para reducir la cantidad de iteraciones y así tardar menos tiempo al momento de recorrer el array.
Al final del post dejaba una pregunta: Y si intentamos generar pequeños compartimientos y reducir aún más las iteraciones?
Hay muchas formas de hacer esto. Podríamos probar con pura matemática, bucles anidados o… creando código dinámicamente.
Posiblemente no necesitemos hacer nada de esto en la gran mayoría de escenarios, pero siempre es interesante ver hasta dónde un lenguaje puede llegar. Y JavaScript es uno de esos lenguajes que nos deja volar la imaginación y hacer cosas que en otros lenguajes sería muy complicado (O imposible).
Entonces, veamos una solución dinámica.
const constructFunction = (steps) => {
let s = "return ";
for (let index = 0; index < steps; index++) {
s += `(arr[i * ${index * steps}] > arr[(i * ${index * steps}) + 1]) || `;
}
s = s.substr(0, s.lastIndexOf(" ||")) + ";";
return new Function("i", "arr", s);
};
Lo primero que necesitamos es una función que nos permita crear código en tiempo de ejecución. Esta función genera estos pseudo compartimientos en base a la cantidad de los mismos y haciendo que el “cursor” del array “salte” las distancias de los compartimientos en cada iteración. El constructor “Function” nos permite crear una función en JavaScript basándose en el texto pasado por parámetros. Esto funciona de forma similar a “eval” con la diferencia que es ligeramente más seguro.
El siguiente paso es modificar el cuerpo de la función que valida el ordenamiento para que pueda crear y usar esta función.
const isSorted = (a, steps) => {
if (a.length <= 1) return true;
const partitions = constructFunction(steps);
for (let index = 0; index < steps; index++) {
if (partitions(index, a) === true) return false;
}
return true;
};
La navegación del array ahora se limita a la cantidad de compartimientos y no a todo el array. Por lo tanto, mientras más compartimientos tengamos menos iteraciones. Por supuesto, habrá más condiciones de comprobación (Todo tiene sus pros y sus contras). Por último, la ejecución.
const number_array = [1, 2, 3, 6, 9, 10, 30, 31, 88];
console.log(isSorted(number_array, number_array.length / 3));
Es importante aclarar que el código anterior es solo para ejercitarnos pero no debe ser usado directamente salvo que le hagamos modificaciones importantes. Por ejemplo, el cálculo de los compartimientos no es correcto y es necesario calcular de forma específica cuando el array no genera compartimientos enteros. De cualquier manera, y como decía al principio, es interesante para pensar una solución desde una mirada diferente.
