Page 44 - revista 2019

Revista de la Facultad de Ingeniería, Año 6, Número 1

Figura 2: Ejemplo de Quicksort. Los pivotes están subrayados. Las
líneas punteadas representan la división en menores y mayores que el
pivote, y las líneas continuas muestran la unión de sub-arrays
(ordenados recursivamente) y pivotes.

En JavaScript se puede implementar como en el listado 2.

const quicksort = arr => {
if (arr.length < 2) {
return arr;
} else {
const pivot = arr[0];
const smaller = arr.slice(1).filter(x => x < pivot);
const greaterEqual = arr.slice(1).filter(x => x >= pivot);
return [
...quicksort(smaller),
pivot,
...quicksort(greaterEqual)];
}
};
Listado 2: Quicksort. El caso base es ordenar un array de menos de dos
elementos. La notación arr.slice(1) retorna todos los elementos de
arr salvo el primero, y arr.filter(…) produce un nuevo array con los
elementos que cumplan con cierta condición.

Un ejemplo de la vida real

Los ejemplos vistos arriba son casos más “reales” que los usualmente mostrados al
ilustrar recursividad, pero no representan problemas con que debamos lidiar
frecuentemente. Pasemos ahora a ver un requerimiento de la vida real, que enfrenté
en un proyecto con un cliente.
Tenemos una serie de campos a imprimir en formato tipo tabla, para generar un PDF
que el usuario descargará. Cada campo tiene contenidos (no relevantes aquí) y un
ancho mínimo que precisa. No podemos cambiar el orden de los campos. Debemos
presentarlos de modo justificado con márgenes parejos (véase la figura 3) sin agregar
demasiado espacio en blanco.

43