Algoritmos de ordenación para principiantes en JavaScript: Burbuja, Selección y Ordenación por inserción

Tener sus conjuntos de datos ordenados de forma voluntaria solo agregará más tiempo y recursos para administrar y buscar. Si sus datos están ordenados o no, afectará directamente a los métodos de búsqueda que puede usar y puede significar la diferencia entre una búsqueda que requiere un millón de operaciones o 10, como con la búsqueda binaria.

Por simplicidad, solo nos centraremos en ordenar una matriz de números de menor a mayor, pero estos algoritmos son fácilmente modificables para otros objetivos de clasificación. Tenga en cuenta que estos son conceptos y patrones más generales y menos «cómo hacer» para ordenar los datos, ya que su implementación en particular puede diferir mucho, pero al final puede parecerse conceptualmente a estos patrones.

Aquí está la matriz de práctica de 50 números aleatorios.

const unsortedArr = ;

Requisitos previos

Voy a mirar todo a través de la lente de la notación Big O, por lo que comprender cómo crece la complejidad con el tiempo será muy útil.

Bubble Sort

Este es el «Hola Mundo» de los métodos de selección, nada loco, pero hace el trabajo.

Para cada elemento de la matriz queremos comprobar si el siguiente elemento es más grande, si es entonces intercambiar sus índices en la matriz. Para evitar recompar números ordenados, comenzaremos desde la parte posterior de la matriz, mientras que otro for loop obtiene el número anterior. De esta manera, todos los valores más grandes se acumulan, o «burbujean», en el extremo.

Animación de clasificación de burbujas

Gráfico/Animación gracias a VisuAlgo.net

Nuestra versión funciona a la inversa de la animación, pero está lo suficientemente cerca.

const bubble = arr => { const swap = (list, a, b) => , list] = , list]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr > arr) swap(arr, j, j + 1); }; }; return arr;};console.log(bubble(unsortedArr));

Clasificación de selección

La clasificación de selección funciona como lo opuesto a la clasificación de burbujas, mientras que la clasificación de burbujas empuja todos los valores más grandes al final ahora vamos a empujar los valores mínimos al principio.

Cada vez que hace un bucle sobre la matriz, selecciona el valor más pequeño, si encuentra un valor más bajo, entonces se convierte en el nuevo valor más bajo. Cuando el bucle esté terminado, tomará ese mínimo y lo colocará en la parte frontal de la matriz antes de comenzar el bucle de nuevo. De esta manera, el valor más bajo de cada iteración se apila en el frente hasta que se ordena toda la matriz.

 Selección Ordenar Animación

Gráfico/Animación gracias a VisuAlgo.net

const selection = arr => { const swap = (list, a, b) => , list] = , list]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr < arr) min = j; }; swap(arr, i, min); }); return arr;};console.log(selection(unsortedArr));

Ordenación por inserción

Mi favorito personal y el más eficiente de los tres, ordenación por inserción, es más similar a cómo clasificaría algo a mano.

Vemos el array como dos partes, la ordenada y la no ordenada, con cada vez que encontramos un nuevo valor que hacemos un bucle para encontrar su lugar en la mitad ordenada. Con cada adición, nuestro grupo ordenado crece hasta que es todo el array.

 Animación de ordenación por inserción

Gráfico/Animación gracias a VisuAlgo.net

const insertion = arr => { arr.forEach((item, i) => { let num = arr; let j; for (j = i - 1; j >= 0 && arr > num; j--) { arr = arr; }; arr = num; }); return arr;};console.log(insertion(unsortedArr));

Comparación

Un problema con el uso de la notación Big O para comparar algoritmos es que se basa en el peor de los casos, que puede ser el mismo en todos los algoritmos, dando la falsa ilusión de que son iguales. Si bien las clases de burbujas, Selección e inserción son todas O(n^2), eso no nos dice mucho sobre el escenario promedio o el mejor de los casos o cómo varían con la estructura de datos.

La clasificación de inserción gana cada vez. También tiene la ventaja de no necesitar tener toda la matriz antes de comenzar, lo que le permite ordenar las cosas en tiempo real a medida que ingresan los datos.

Tenga esto en cuenta porque no debe decidir qué algoritmo es «mejor» antes de considerar cómo sus datos ya están organizados.

Conclusión

Estas tres soluciones distan mucho de ser las mejores para ordenar de manera eficiente grandes cantidades de datos, pero son algunas de las más intuitivas para sumergir los dedos de los pies en lo que puede ser un océano abrumador. 🌊