Ordenar por inserción en JavaScript
- Técnicas de clasificación en JavaScript
- Implementar la técnica de ordenación por inserción en JavaScript
Este artículo discutirá la idea de Ordenar por Inserción en JavaScript y brindará un ejemplo de su implementación.
Técnicas de clasificación en JavaScript
Las personas interesadas desarrollaron un montón de técnicas de clasificación con la visión de garantizar la optimización, la aceleración y menos espacios. En esta ejecución, la ordenación por inserción muestra que la complejidad temporal del peor de los casos es O(n^2), mientras que el mejor de los casos es O(n).
Para ordenar una pequeña cantidad de datos, Array.prototype.sort() es una buena opción. Como situación preferible, da una complejidad temporal de O(n), que es mejor que O(n*logn).
Sin embargo, la función sort() no funciona bien para una enorme pila de datos con objetos complejos, etc. La función Array.prototype.sort() tiene la implementación de la ordenación por inserción y, por lo tanto, el algoritmo de clasificación predeterminado de JavaScript. no está en la categoría eficiente.
También se debe tener en cuenta que el rendimiento de la clasificación de un código depende del navegador que esté utilizando el usuario. El Chrome V8 usa Tim Sort (inserción Sort + Merge Sort), y Firefox usa Merge Sort básico.
En el escenario de la vida real, los datos sin procesar no están necesariamente desordenados. En cambio, siguen un patrón de orden. Por lo tanto, puede decir que no es necesario ordenar los datos desde cero.
Para el V8, la matriz se divide inicialmente en bloques denominados ejecutar. Estas “ejecuciones” en el nivel inferior se ordenan con el principio de ordenación por inserción y luego se fusionan con el método de ordenación por fusión.
Si está trabajando con algunos números u objetos, Tim Sort se comportará como una inserción de tipo con una complejidad de tiempo de O(n). Mientras que en el caso de grandes datos, V8 Sort funcionará como Merge Sort con la complejidad de tiempo de O(n*logn).
Por lo tanto, Tim Sort es una técnica de clasificación estable y altamente optimizada que la tradicional Merge Sort.
En nuestra sección de ejemplos, cubriremos la idea básica de una ordenación por inserción y le permitiremos determinar por qué tiene sus limitaciones y por qué podría ser mejor que muchas. La discusión de la parte anterior describe cómo se usa la ordenación por inserción en el motor V8, ya que es un motor de JavaScript.
Saltemos a la demostración.
Implementar la técnica de ordenación por inserción en JavaScript
La idea básica de este tipo se puede comparar con clasificar una mano de cartas. Inicialmente configuramos una tarjeta como la primera y luego seleccionamos las siguientes tarjetas para ordenar, denominadas la primera tarjeta configurada.
Aquí, la siguiente carta se nombra como clave, y cuando la clave es mayor que la primera carta, entonces la mantenemos como está; en caso contrario, intercambiamos la posición de la llave y la primera carta. Y esto se repite hasta que toda la matriz se atraviesa y clasifica.
Revisemos las líneas de código.
Fragmento de código:
var arr = [4, 2, 3, 1, 7];
var size = arr.length;
for (var i = 1; i < size; i++) {
var key = arr[i];
var j = i - 1;
while (key < arr[j] && j >= 0) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
console.log(arr)
Producción:
Como podemos ver, Insertion Sort tiene una complejidad de espacio de O(1) ya que no ocupa ninguna otra matriz de espacios para almacenar la clave en lugar de la ranura 1. Entonces, si está consciente del espacio óptimo, este tipo podría encajar bien.
