Este es el segundo artículo en la serie sobre entrevistas para ingenieros Frontend. Si te perdiste el primer artículo, puedes leerlo aquí: Introducción al Rendimiento de Algoritmos y Algoritmos de Búsqueda.

Pre-requisitos

• Conocimiento intermedio de JavaScript (ciclos, objetos, arreglos)
• Conocimiento básico de Big O y Recursión (Introducción al Rendimiento de Algoritmos y Algoritmos de Búsqueda)
• Conocimiento de ES6 (arrow functions)

Cómo correr los ejemplos

Durante este artículo estaré utilizando repl.it para demostrar los ejemplos. Cada ejemplo tendrá un enlace donde podrás correr el código. Además, podrás hacerle fork para que experimentes con el algoritmo o añadas notas.

Al entrar a los enlaces de repl.it podrás darle play o Run al algoritmo para ver el resultado. Para ver el código, presiona Show files. Puedes copiarlo a tu cuenta presionando Fork repl.

Además, incluyo enlaces a visualizaciones de los algoritmos con sonido en Youtube.

Introducción

Los algoritmos de ordenación te permiten organizar los elementos de una lista de alguna manera. Podría ser de manera alfabética, ascendente, descendente, etc. Es un proceso que se realiza a menudo en el mundo de la programación, por lo que no debe sorprender que hay muchísimos algoritmos para este tipo de tarea. Cada técnica tiene sus pros y sus contras. Cuál es el mejor para ti dependerá de tu contexto.

En este artículo hablaré sobre los algoritmos de ordenación más comunes. En todos los ejemplos ordenaremos el arreglo nums de manera ascendente.

Bubble Sort

La ordenación de burbuja es uno de los algoritmos mejor conocidos por su terrible rendimiento. Evalúa la lista por pares. Compara cada elemento con su sucesor y los intercambia si es necesario para que el par esté ordenado. Mostraré dos versiones del algoritmo, la primera utiliza recursión.

Pseudo Code

• Empieza un ciclo que recorra el arreglo desde el final hasta el principio. Utiliza una variable para saber en qué punto del arreglo estás. Utilizaré la i para este ciclo.
• Dentro del primer ciclo, inicializa otro que recorra el arreglo desde el principio hasta uno menos que la variable del ciclo anterior. Para este ciclo, utilizaré la j
• Si arreglo[j] es mayor que arreglo[j+1] intercambia los valores
• No olvides devolver el arreglo ordenado

✨ Visualización ✨

Implentación

Estaremos mirando dos maneras de escribir este algoritmo, iterativamente y con recursión.

Iterativa

✨Replit Iterativo✨

Recursión

✨ Replit Recursión ✨

Selection Sort

Selection Sort recorre todo el arreglo hasta seleccionar el elemento que cumple con los criterios de ordenación que hemos impuesto. Por ejemplo, si deseamos ordenar un arreglo compuesto de enteros de manera ascendente, estaríamos buscando el número más pequeño del arreglo. Luego, lo intercambiamos con el primer valor del arreglo que no haya sido ordenado. De esta manera, se van creando dos sub-listas, una ordenada y otra por ordenar.

Pseudo Code

• Crea una variable para seguir el rastro del valor más pequeño en la lista. Será inicializada con el primer elemento del arreglo
• Compara el valor de este elemento con el próximo en la lista hasta encontrar un valor menor
• Si encuentras un valor menor, guárdalo.
• Continúa hasta el final del arreglo
• El valor menor es diferente al valor con el que comenzaste, intercámbialos
• Repite estos pasos hasta terminar de ordenar la lista
• Devuelve el arreglo ordenado

✨ Visualización ✨

Implentación

✨ Replit ✨

Insertion Sort

Al igual que Selection Sort, el algoritmo de ordenación por inserción envuelve tomar un valor y compararlo con los demás en el arreglo. En este caso, empezamos con el segundo valor en el arreglo y lo comparamos con el primero. Si este es mayor que el primero, lo insertamos a la izquierda de este y nos movemos al próximo valor en el arreglo. Comparamos este valor con los valores anteriores hasta encontrar su lugar en la ordenación. Obtiene un valor y lo pone en el lugar correspondiente; por eso es útil para ordenar elementos que van entrando poco a poco. No es necesario tener la lista completa al inicio.

Pseudo Code

• Guarda el segundo valor del arreglo en alguna variable
• Compáralo con el valor del elemento anterior. Intercámbialos si este es mayor
• Muévete al próximo valor y compáralo con los anteriores hasta encontrar su lugar. Insértalo en su lugar correspondiente, de ser necesario
• Repite hasta ordenar todo el arreglo

✨ Visualización ✨

Implentación

✨ Replit ✨

Estos tres algoritmos tienen una complejidad espacial constante pues no crean una nueva variable en cada iteración del ciclo ni estamos creando un arreglo nuevo. Todos los cambios se hacen directamente en el arreglo original. Ninguno de estos algoritmos es ideal para listas grandes pues su rendimiento en relación con el tamaño de entrada es terrible. Los próximos algoritmos, aunque más complicados, tienen mejor rendimiento con una complejidad de O(n log n).

Merge Sort

Este algoritmo parte de dos conceptos – unir y ordenar. Divide la lista de entrada continuamente hasta que solo tiene muchos arreglos con un elemento. Cada uno de estos sub-arreglos ya están ordenados al tener solo un elemento. Luego, une dos arreglos y los ordena, hasta tener nuevamente un solo arreglo con todos los elementos originales ordenados. Es uno de los algoritmos de ordenación con mejor rendimiento, pero no viene sin su desventaja. Merge sort es, probablemente, el algoritmo más complicado en este artículo. Tómalo como un desafío, pero no te sientas mal si no te sale.

Para dividir el trabajo y organizar el algoritmo, es útil crear dos funciones. La primera se encargará de dividir la lista original en dos recursivamente hasta tener cada elemento de la lista original en su propio arreglo. A esta le llamaremos mergeSort(arr). La segunda, aceptará dos arreglos previamente ordenados y devuelve un solo arreglo ordenado. Esta será merge(arr1, arr2).

✨ Visualización ✨

Pseudo Code Merge()

• Crea un arreglo vacío – a este le estaremos añadiendo los valores ordenados. Le puedes llamar de cualquier manera, pero en este artículo le llamaremos result. const result = [];
• Nos interesa el valor menor de cada arreglo
• Si el valor en el primer arreglo es menor que el valor en segundo arreglo, pon el valor del primer arreglo en result utilizando el método Array.prototype.push()
• Continua con el próximo valor en el primer arreglo
• Si el valor del primer arreglo es mayor que el valor del segundo arreglo, empuja el valor del segundo arreglo a result
• Continua con el próximo valor en el segundo arreglo
• Cuando uno de los arreglos ya esté vacío, une los valores que queden en el otro con el arreglo result

Implementación Merge()

Pseudo Code MergeSort()

• Si el arreglo tiene solo un elemento, devuelve el elemento, ya que está implícitamente ordenado
• Encuentra el centro del arreglo
• Divide el arreglo por la mitad y cada mitad por la mitad hasta solo tener arreglos de un elemento
• Envía las mitades a merge() y devuelve su resultado

Implentación MergeSort()

La complejidad de este algoritmo es igual para el peor caso, el mejor caso, y el caso promedio. Siempre hace lo mismo: rompe un arreglo en arreglos con un solo elemento y vuelve a unirlos. Qué tan ordenada está la lista original no influye para nada en la complejidad. Big O para mergeSort() es O(n logn). Como crea un nuevo arreglo por cada elemento en la lista, la complejidad espacial, la cantidad de memoria que utiliza, es O(n).

✨ Replit Merge Sort ✨

Quick Sort

Al igual que el anterior, este algoritmo divide una lista en dos recursivamente. En este caso, no se dividen estrictamente por la mitad, sino que podemos escoger cualquier punto en la lista como pivote. Lo importante es que al recorrer el arreglo, acomodemos todos los valores menores que el pivote en una sub-lista a la izquierda del pivote.

Todo lo que sea mayor, va en una sub-lista a la derecha del pivote. Para lograr esto, creamos una función de utilidad. Estas dos sub-listas, luego, son enviadas a la función quickSort() individualmente. Con el resultado de estas dos llamadas, organizas todo en un arreglo ordenado.

Escoger el pivote es crucial para obtener un rendimiento óptimo. Idealmente, conocemos el valor mediano en la lista. Otras estrategias pueden ser escoger el primero, el último, el del medio, o valor aleatorio. En este artículo trabajaré con el primer valor como pivote.

✨ Visualización ✨

Pseudo Code

• Escoge el pivote
• Coloca todos los valores menores al pivote en un arreglo que llamaremos smaller y los mayores en un arreglo que llamaremos bigger
• Envía cada lista a quickSort() de manera independiente
• Une los resultados de esas llamadas y el pivote para que queden en orden. Primero van los valores en el arreglo smaller, luego el pivote, y por último los valore en el arreglo bigger

Implentación

Radix Sort

Hasta el momento, todos los algoritmos que hemos visto hacen comparaciones para ordenar.

Radix Sort es el único en este artículo que no hace comparaciones. Solo ordena listas de números. Para ordenar otro tipo de data, debes primero convertirla a binario para cumplir con este requisito. El algoritmo se deja llevar por el hecho de que mientras más dígitos tiene un número, mayor es.

Crearemos diez cajas, una para cada dígito, ya que utilizaremos base diez. Es posible utilizar otras, pero esta es la más simple. Acomodaremos los números en la caja correspondiente al último dígito de del número.

Utilizado el orden en el que se encuentran en las cajas, creamos una lista. Luego, repetiremos el mismo proceso, esta vez dejándonos llevar por el dígito antepenúltimo, y así sucesivamente hasta tener una lista ordenada. Haremos esto unas L veces, donde L es la cantidad de dígitos que tiene el número más grande en nuestra lista.

✨ Visualización ✨

Necesitaremos tres funciones de utilidad que nos ayudarán en la función de Radix.

getDigit()

Esta función aceptará un número de nuestra lista y el número correspondiente a la posición del dígito que queremos. La posición del dígito se contará al revés de los índices. Empezaremos el conteo en cero desde el dígito en la extrema derecha.

getNumberLength()

longestDigitCount()

Pseudo Code Radix Sort

• Encuentra L
• Crea un ciclo que vaya de 0 a L
• En cada iteracción, crea cajas para cada dígito
• Crea un nuevo arreglo basado en las cajas creadas. Une las cajas en orden ascendente
• Devuelve el nuevo arreglo

Implentación

La complejidad de este algoritmo es basada en la cantidad de veces que hay que recorrer la lista y la cantidad de dígitos promedio de los números en la lista. Nos referimos a la cantidad de veces que hay que recorrer la lista como n y la cantidad de dígitos como k. Entonces, la complejidad es O(nk).

✨ Replit Radix Sort ✨

Array.prototype.sort()

El método integrado en los arreglos de JavaScript para ordenación es .sort(). Ordena el arreglo localmente—quiere decir que muta el arreglo original—y devuelve el arreglo ordenado. Este método puede ser muy útil, pero puede generar resultados inesperados. Por eso, debemos saber cómo funciona y cómo podemos manipularlo para obtener los resultados correctos.

Vamos a ordenar el siguiente arreglo de manera ascendente.

const nums = [2, 4, 1, 10, 3, 19, 6];

¿Cómo crees que se vería el resultado?

El resultado es el siguiente.

Oye, pero ¿no es 10 mayor que 2 y que 3 y que 4 y que 6? ¿No deberían ir el 10 y el 19 al final de la lista?

Eso mismo pensé la primera vez que utilicé este método para ordenar los duplicados de un objeto en la primera aplicación en la que trabajé. La documentación indica lo siguiente:

• ordena los elementos de un arreglo en su mismo lugar (no crea otro arreglo) y devuelve el arreglo ordenado
• de manera predeterminada, el orden de clasificación es ascendente al convertir los elementos del arreglo en strings para luego comparar las secuencias de su valor de UTF-16
• el rendimiento (Big O) no puede ser garantizado ya que depende de la implementación

Es por el segundo punto que el resultado no es lo que esperamos.

La documentación también explica que podemos pasarle una función para que la utilice para comparar. Esta función debe aceptar dos elementos para comparar. Para esto, puedes escribir una función y luego pasarle el nombre al método de ordenación o puedes hacerla justo en el método. En el siguiente ejemplo demuestro cómo podemos ordenar nums en orden ascendente del valor de los números.

nums.sort((a,b) => a - b); // [1, 2, 3, 4, 6, 10, 19]

Para ordenarlo de manera descendente, solo invertimos la resta a b - a.

También podemos ordenar un arreglo compuesto de objetos.

Tomemos el siguiente objeto.

Para ordenar los objetos de manera ascendente por edad modificamos la función de comparación anterior.

En español, las palabras tienen acentos y otros símbolos que no se utilizan en inglés. Esto altera los resultados de una ordenación. Para tenerlos en cuenta, utilizamos [[String.localeCompare]](<https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/localeCompare>)

Vamos a ordenar las siguientes palabras de manera ascendente.

const palabras = ["salimos", "salí", "sal", "sales"];

Algoritmo Utilizado Por Buscadores

Por su alto rendimiento y estabilidad, Merge Sort es el algoritmo más utilizado por los buscadores para definir Array.prototype.sort(). Ocasionalmente, encontrarás buscadores que utilizan Quick Sort, o alguna variante de este, en su lugar.

Conclusión

En cuanto a estabilidad y rendimiento espacial, merge sort es la mejor opción de esta lista. También es una buena opción para ordenar linked lists. Si la lista de entrada es pequeña o está casi ordenada, insertion sort puede ser una buena alternativa.

Estos algoritmos nos proveen una base para ordenar datos en nuestras aplicaciones, pero no son las únicas posibilidades. Puedes usarlos como guía para construir tus propias soluciones sabiendo qué rendimiento esperar de ciertos comportamientos.

Recursos

La Guía Definitiva de Métodos de Arreglos

Visualización de Algoritmos de Ordenación

15 Algoritmos de Ordenación en 6 Minutos

MDN Array.prototype.sort()

MDN String.localeCompare

Animación de Algoritmos de Ordenación

MDN Spread

Radix Helpers