Combinar ordenación en JavaScript

En este artículo, veremos uno de los algoritmos de clasificación más populares: Merge Sort. También explicaremos la implementación y veremos la eficiencia.

Introducción

Ordenar se refiere a organizar los elementos de una lista en un orden específico (numérico o alfabético). La clasificación se usa generalmente junto con la búsqueda.

Por lo general, es más fácil buscar un elemento (llamado clave) en una lista dada si la lista está ordenada, tanto visual como algorítmicamente.

Hay muchas formas (algoritmos) de ordenar una lista dada de elementos. Merge Sort es una de las formas más populares y eficientes de hacerlo.

En este artículo, veremos la lógica detrás de Merge Sort, la implementaremos en JavaScript y la visualizaremos en acción. Finalmente, compararemos Merge Sort con otros algoritmos en términos de complejidad espacial y temporal.

Comprensión de la lógica detrás de la ordenación por fusión {#comprensión de la lógica detrás de la ordenación por fusión}

La ordenación por combinación utiliza el concepto de divide y vencerás para ordenar la lista de elementos dada. Descompone el problema en subproblemas más pequeños hasta que se vuelven lo suficientemente simples como para resolverlos directamente.

Estos son los pasos que toma Merge Sort:

  1. Divida la lista dada en dos mitades (mitades aproximadamente iguales en el caso de una lista con un número impar de elementos).
  2. Continúe dividiendo los subarreglos de la misma manera hasta que se quede con arreglos de un solo elemento.
  3. Comenzando con los arreglos de un solo elemento, combina los subarreglos para que cada subarreglo combinado esté ordenado.
  4. Repita la unidad del paso 3 para terminar con una sola matriz ordenada.

Echemos un vistazo a cómo funciona Merge Sort en una matriz como [4, 8, 7, 2, 11, 1, 3]:

Ejemplo de clasificación combinada

Implementación de Merge Sort en JavaScript

Primero escribamos código para combinar() dos subarreglos ordenados en un arreglo ordenado. Es muy importante tener en cuenta que ambos subconjuntos ya están ordenados, y solo los estamos combinando usando la función merge().

Podemos hacer esto repasando estos dos subarreglos y agregando uno por uno los elementos para que el arreglo resultante también se ordene:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function merge(left, right) {
    let arr = []
    // Break out of loop if any one of the array gets empty
    while (left.length && right.length) {
        // Pick the smaller among the smallest element of left and right sub arrays 
        if (left[0] < right[0]) {
            arr.push(left.shift())  
        } else {
            arr.push(right.shift()) 
        }
    }
    
    // Concatenating the leftover elements
    // (in case we didn't go through the entire left or right array)
    return [ ...arr, ...left, ...right ]
}

En esta función, tomamos dos subarreglos ordenados (left, right) y los fusionamos para obtener un solo arreglo ordenado. Primero, creamos una matriz vacía. Más tarde, elegimos el más pequeño de los elementos no seleccionados más pequeños en los subarreglos ‘izquierdo’ y ‘derecho’ y los colocamos en el conjunto vacío. Solo necesitamos verificar los primeros elementos en los subarreglos ‘izquierdo’ y ‘derecho’ ya que ambos están ordenados.

Al hacer esto, eliminamos el elemento elegido del subarreglo (esto se logra usando la función shift()). Continuamos este proceso hasta que uno de los subarreglos se vacía. Después de eso, empujamos los elementos sobrantes del subarreglo no vacío (porque ya están ordenados) al arreglo principal.

Como ahora tenemos el código para fusionar dos matrices ordenadas (conquer parte de divide-and-conquer), escribamos el código final para nuestro algoritmo Merge Sort. Esto significa que debemos seguir dividiendo matrices, hasta que terminemos con matrices que solo contienen un elemento:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function mergeSort(array) {
  const half = array.length / 2
  
  // Base case or terminating case
  if(array.length < 2){
    return array 
  }
  
  const left = array.splice(0, half)
  return merge(mergeSort(left),mergeSort(array))
}

Aquí, identificamos el punto medio y dividimos el arreglo en dos subarreglos usando la función splice(). Si hay un número impar de elementos, el de la izquierda obtiene un número menor de elementos. Estamos dividiendo hasta que nos quedan matrices de un solo elemento (array.length < 2). Después de eso, comenzamos a combinar los subarreglos usando la función merge() previamente escrita.

Ahora que tenemos el código en su lugar, veamos el resultado de ejecutar la función en nuestro ejemplo anterior:

1
2
array = [4, 8, 7, 2, 11, 1, 3];
console.log(mergeSort(array));

Lo que nos da el resultado esperado:

1
1,2,3,4,7,8,11

La eficiencia de la ordenación por combinación

La complejidad temporal del peor caso de Merge Sort es O(nlogn), la misma que la complejidad temporal del mejor caso de Ordenación rápida. Cuando se trata de velocidad, Merge Sort es uno de los algoritmos de clasificación más rápidos que existen.

A diferencia de Quick Sort, Merge Sort no es un algoritmo de clasificación en el lugar, lo que significa que ocupa espacio adicional además de la matriz de entrada. Esto se debe a que estamos utilizando matrices auxiliares (ayudantes) para almacenar las sub-matrices. La complejidad espacial del ordenamiento por fusión es O(n).

Otra ventaja de Merge Sort es que se presta muy bien a subprocesos múltiples, ya que cada mitad respectiva se clasifica por sí solo. Otra forma común de reducir el tiempo de ejecución de Merge Sort es detenerse cuando lleguemos a subarreglos relativamente pequeños (~7) y usar Tipo de inserción para ordenarlos.

Esto se hace porque la ordenación por inserción funciona muy bien en matrices pequeñas o casi ordenadas. Mucho mejor que sus contrapartes más eficientes a nivel mundial.

Conclusión

En este artículo, hemos visto la lógica detrás del algoritmo Merge Sort, cómo implementarlo en JavaScript y hemos aprendido sobre su rendimiento. Es uno de los algoritmos de clasificación básicos y es realmente útil para dar un ejemplo claro de la estrategia divide y vencerás.