Algoritmos de ordenamiento para principiantes en JavaScript: ordenamiento por burbuja, selección e inserción

Si organiza sus conjuntos de datos de cualquier manera, solo le restará tiempo y recursos para administrarlos y buscarlos. El hecho de que sus datos estén ordenados o no afectará directamente los métodos de búsqueda que puede utilizar y puede significar la diferencia entre una búsqueda que requiera un millón de operaciones o que requiera 10, como ocurre con la búsqueda binaria.

Para simplificar, nos centraremos únicamente en ordenar una matriz de números de menor a mayor, pero estos algoritmos se pueden modificar fácilmente para otros objetivos de ordenación. Tenga en cuenta que estos son conceptos y patrones más generales y no tanto una guía para ordenar datos, ya que su implementación 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 = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];

Prerrequisitos

Analizaré todo desde la perspectiva de la notación Big O, por lo que comprender cómo crece la complejidad con el tiempo será muy útil.

Ordenamiento de burbujas

Este es el “Hola mundo” de los métodos de clasificación, nada del otro mundo, pero cumple su función.

Para cada elemento de la matriz, queremos comprobar si el siguiente elemento es más grande; si lo es, intercambiamos sus índices en la matriz. Para evitar tener que volver a comparar los números ordenados, comenzaremos desde el final de la matriz mientras otro for loopobtiene el número anterior. De esta manera, todos los valores más grandes se acumulan o "surgen" al final.

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

Nuestra versión funciona al revés que la animación, pero es bastante parecida.

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

Ordenación por selección

La ordenación por selección funciona de manera opuesta a la ordenación de burbuja, mientras que la ordenación de burbuja empuja todos los valores más grandes hasta el final, ahora vamos a empujar los valores mínimos hasta el principio.

Cada vez que recorre la matriz, selecciona el valor más pequeño y, si encuentra un valor más bajo, se convierte en el nuevo valor más bajo. Cuando finaliza el bucle, toma ese valor mínimo y lo coloca al principio de la matriz antes de comenzar el bucle nuevamente. De esta manera, el valor más bajo de cada iteración se apila al principio hasta que se ordena toda la matriz.

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

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

Ordenación por inserción

Mi favorito personal y el de mayor rendimiento de los tres,ordenación por inserción, es más parecido a cómo ordenarías algo a mano.

Consideramos la matriz como dos partes, la ordenada y la no ordenada. Cada vez que encontramos un nuevo valor, volvemos a buscar su lugar en la mitad ordenada. Con cada adición, nuestro grupo ordenado crece hasta que es la matriz completa.

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

const insertion = arr = {  arr.forEach((item, i) = {    let num = arr[i];    let j;    for (j = i - 1; j = 0  arr[j]  num; j--) {      arr[j + 1] = arr[j];    };    arr[j + 1] = 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 escenario posible, que puede ser el mismo en todos los algoritmos, lo que da la falsa ilusión de que son iguales. Si bien los ordenamientos de burbuja, selección e inserción son todos O(n^2), eso no nos dice mucho sobre el escenario promedio o el mejor escenario posible ni sobre cómo varían con la estructura de datos.

La ordenación por inserción siempre es la mejor opción. También tiene la ventaja de que no es necesario tener toda la matriz antes de comenzar, lo que permite ordenar los datos en tiempo real a medida que llegan.

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

Conclusión

Estas tres están lejos de ser las mejores soluciones para ordenar de manera eficiente grandes cantidades de datos, pero son algunas de las más intuitivas para adentrarse en lo que puede ser un océano abrumador.