Ordenar por inserción en JavaScript

En este tutorial, explicaremos e implementaremos la ordenación por inserción en JavaScript, analizaremos su complejidad temporal y la compararemos con otros algoritmos.

Introducción

En este artículo, explicaremos cuál es la idea detrás de la ordenación por inserción y la implementaremos en JavaScript.

La clasificación por inserción es uno de los algoritmos de clasificación más simples. Es altamente intuitivo, estable, en el lugar y de tipo de comparación.

Un algoritmo de clasificación estable es un algoritmo en el que dos objetos con claves iguales aparecen en el mismo orden en la salida ordenada que aparecen en la matriz de entrada para ser ordenados.

En otras palabras, si un algoritmo de clasificación es estable, los elementos equivalentes conservan sus posiciones relativas después de que se realiza el algoritmo de clasificación.

Un algoritmo in situ es un algoritmo que no utiliza memoria ni estructuras de datos adicionales, reescribiendo las ubicaciones de memoria originales de los elementos en la matriz o lista de entrada.

Finalmente, un algoritmo de comparación es aquel que, durante su ejecución, solo lee elementos de la lista a través de una sola operación de comparación abstracta. Según el tipo de datos y el objetivo, la comparación se puede realizar mediante un operador relacional o mediante una función de comparación personalizada.

A pesar de tener una complejidad de tiempo muy grande para un algoritmo de ordenación, la ordenación por inserción puede ser muy útil, a veces incluso puede superar algunos de los algoritmos de ordenación más eficientes, como Quicksort o Merge Sort, en colecciones pequeñas.

Rara vez se usa como un algoritmo independiente; por lo general, usaría un algoritmo de ordenación rápida como Quicksort y terminaría los últimos “cabos sueltos” con Insertion Sort, ya que es muy eficiente para esa tarea.

Clasificación por inserción

La idea detrás de la clasificación por inserción a menudo se compara con la forma en que las personas clasifican una mano de cartas mientras juegan Rummy.

En este juego de cartas, el crupier reparte cartas a cada jugador. Luego, los jugadores toman una por una las cartas que les han sido entregadas, ordenándolas en su mano en orden ascendente insertando cada carta en su lugar.

Durante todo este proceso, los jugadores tienen una pila de cartas clasificadas en sus manos, mientras que la pila sin clasificar de la que extraen nuevas cartas está frente a ellos.

Una propiedad muy útil de Ordenar por inserción es el hecho de que no necesita conocer la matriz completa de antemano para poder ordenarla; simplemente inserta los elementos dados uno por uno.

Esto realmente es útil cuando queremos agregar más elementos en una matriz ya ordenada, porque la ordenación por inserción agregará los nuevos elementos en sus lugares apropiados sin recurrir a toda la colección.

Aquí hay una representación visual de cómo funciona la ordenación por inserción:

insertion sort visual representation

Implementación de clasificación por inserción

Ahora que entendemos la idea detrás de la ordenación por inserción, podemos pasar a la implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function insertionSort(inputArr) {
    let n = inputArr.length;
        for (let i = 1; i < n; i++) {
            // Choosing the first element in our unsorted subarray
            let current = inputArr[i];
            // The last element of our sorted subarray
            let j = i-1; 
            while ((j > -1) && (current < inputArr[j])) {
                inputArr[j+1] = inputArr[j];
                j--;
            }
            inputArr[j+1] = current;
        }
    return inputArr;
}

La iteración comienza en el segundo elemento. Consideramos el primer elemento ordenado por defecto. Para cada iteración, hacemos un seguimiento del elemento actual. Cada elemento actual será el primer elemento de la matriz no ordenada, y cada elemento anterior pertenecerá a la matriz ordenada.

A través de un bucle while, recorremos la matriz ordenada y cambiamos los elementos a la derecha, abriendo un espacio para que se inserte el elemento actual.

Una vez que encontramos el lugar adecuado para él, el elemento actual se inserta en la ranura recién abierta. Este proceso se repite para cada iteración hasta que se ordena la matriz.

Ahora, completemos una matriz y llamemos a nuestro algoritmo de clasificación:

1
2
3
let inputArr = [5, 2, 4, 6, 1, 3];
insertionSort(inputArr);
console.log(inputArr);

La salida de esta matriz será:

1
(6) [1, 2, 3, 4, 5, 6]

Repasemos este ejemplo paso a paso:

Primera iteración:

Matriz ordenada: 5
Matriz sin ordenar: 2, 4, 6, 1, 3

  • El primer elemento en nuestra matriz desordenada es 2.
  • 2 < 5, entonces movemos 5 un lugar a la derecha.

Matriz ordenada: _, 5

  • 2 se coloca en su lugar correcto.

Segunda iteración:

Matriz ordenada: 2, 5
Matriz desordenada: 4, 6, 1, 3

  • El primer elemento de nuestra matriz desordenada es 4.
  • 4 < 5, entonces movemos 5 un lugar a la derecha.

Matriz ordenada: 2, _, 5

  • 4 !< 2, por lo que no movemos 2.
  • 4 se coloca en su lugar correcto.

Tercera Iteración:

Matriz ordenada: 2, 4, 5
Matriz desordenada: 6, 1, 3

  • El primer elemento de nuestra matriz desordenada es 6.
  • 6 !< 5, por lo que no movemos 5.

Matriz ordenada: 2, 4, 5

  • 6 se coloca en su lugar correcto.

Esto se repite hasta que nos recibe una matriz ordenada: 1, 2, 3, 4, 5, 6.

Podemos notar un invariante en cada una de estas iteraciones. Para la iteración k-ésima de nuestro bucle, se garantiza que el intervalo de [0,k] se ordenará.

Comparación de tiempo {#comparación de tiempo}

El mejor tiempo de ejecución de la ordenación por inserción es lineal y lo obtenemos si nuestra matriz de entrada ya está ordenada. Esto significa que la ordenación por inserción funciona de maravilla cuando se trata de verificar si la matriz está ordenada o no.

Sin embargo, la complejidad de tiempo promedio y peor es O(n^2^), lo cual es bastante malo para un algoritmo de clasificación, especialmente cuando se aplica a matrices o listas de mayor tamaño. En este caso, Quicksort o Merge Sort con una complejidad de O(nlogn) serían una opción mucho mejor.

On the other hand, being one of the fastest quadratic sorting algorithms, Insertion Sort usually outperforms Ordenamiento de burbuja, Gnome Sort and Clasificación de selección. In addition to that, when our input array size is very small (10-20 elements), Insertion Sort can even outperform Quicksort and Merge Sort.

Esta es la razón por la cual JavaScript, a pesar de usar Quicksort (en Chrome) o Merge Sort (en Mozilla) como el algoritmo de clasificación principal, también usa Insertion Sort en colecciones pequeñas, y después de que Quicksort/Merge Sort haya hecho la mayor parte del trabajo.

Conclusión

La ordenación por inserción es un algoritmo de ordenación de comparación simple, estable e in situ.

A pesar de consumir bastante tiempo con la complejidad cuadrática, es muy útil cuando la matriz de entrada es de tamaño pequeño. En este caso, incluso supera a los algoritmos de divide y vencerás más utilizados, razón por la cual JavaScript usa una combinación de ordenación por inserción y ordenación por fusión o ordenación rápida cuando se usan funciones de ordenación integradas.

Cuando se trata de matrices de mayor tamaño, supera a la mayoría de los demás algoritmos de clasificación cuadrática, incluidos Bubble Sort, Gnome Sort y Selection Sort. Sort.