Introducción a la ordenación por inserción en JavaScript
La clasificación es uno de los conceptos importantes que los programadores aprenden a comenzar su viaje en informática independientemente del lenguaje de programación seleccionado para aprender. La clasificación nos ayuda a localizar los datos de destino que queremos buscar de una manera más rápida y conveniente, ordenándolos en orden ascendente o descendente.
Los algoritmos de clasificación se utilizan para reordenar elementos, donde un elemento puede ser un número o una cadena. Existen muchos tipos de algoritmos de clasificación basados en su método de clasificación y el enfoque que siguen para clasificar los elementos, y cada tipo tiene sus ventajas y desventajas.
En este blog, nos centraremos en el tipo de inserción, un tipo común que es fácil de entender e implementar.
¿Qué es el orden de inserción en JavaScript?
El método de inserción es un algoritmo simple y fácil de entender que funciona mejor con una pequeña lista de datos al ordenar cada elemento en la lista de datos uno por uno de izquierda a derecha. También se conoce como una clasificación de comparación donde compara el valor actual con los otros valores dentro de la misma lista de datos que se está ordenando. Sigue un enfoque iterativo para colocar cada elemento en el orden correcto en la lista de datos.
Cuanto más tiempo toma ordenar un algoritmo, se dice que su rendimiento es malo y necesita considerar otro algoritmo para ordenar los datos. La ordenación por inserción tiene una complejidad temporal de O (n²) o ejecuta un tiempo cuadrático para ordenar la lista de datos en el peor de los casos. Esto generalmente no es muy efectivo y no debe usarse para listas grandes. Sin embargo, generalmente supera a los algoritmos avanzados, como quicksort o mergesort en listas más pequeñas.
Ordenación por inserción, la mayoría de las veces es más eficiente que otros algoritmos de ordenación cuadrática como la ordenación por burbuja o la ordenación por selección. Su mejor escenario, el tiempo es O (n), o lineal, que ocurre si la matriz de entrada ya está ordenada. En promedio, el tiempo de ejecución de la ordenación por inserción sigue siendo cuadrático.
En el siguiente ejemplo, tendremos un enfoque fácil de alto nivel para ordenar los datos almacenados en una estructura de datos de matriz y usar su método de clasificación para ordenar los datos sin implementar ningún algoritmo.
Ejemplo: Algoritmo de clasificación de inserción
Código:
// Declaring unsorted data and storing it in array data structure
var dataArray = (96, 5, 42, 1, 6, 37, 21) // Function - Insertion Sort Algo.
function insertSort(unsortedData) (
for (let i = 1; i < unsortedData.length; i++) (
let current = unsortedData(i);
let j;
for(j=i-1; j >= 0 && unsortedData(j) > current;j--) (
unsortedData(j + 1) = unsortedData(j) )
unsortedData(j + 1) = current;
)
return unsortedData;
)
// print sorted array
console.log(insertSort(dataArray));
Salida:
Explicación: En el algoritmo, hemos implementado 2 bucles for, el bucle for externo es iterar sobre los elementos de la matriz y el bucle for interno se usa para ordenar los elementos de la matriz en el orden ascendente de su valor. La variable actual contiene el valor actual de la matriz y la variable j se establece en un valor menor que la posición de índice actual de la matriz. Verificamos si el elemento actual (actual) es más pequeño que el valor de la matriz en la posición j (unsortedData (j) ) y si es cierto, clasificamos esos valores.
Iteración 1 - actual (96): (96, 5, 42, 1, 6, 37, 21)
Iteración 2 - actual (5): (5, 96, 42, 1, 6, 37, 21)
Iteración 3 - actual (42): (5, 42, 96, 1, 6, 37, 21)
Iteración 4 - actual (1): (1, 5, 42, 96, 6, 37, 21)
Iteración 5 - actual (6): (1, 5, 6, 42, 96, 37, 21)
Iteración 6 - actual (37): (1, 5, 6, 37, 42, 96, 21)
Iteración 7 - actual (21): (1, 5, 6, 21, 37, 42, 96)
La iteración externa para el bucle comienza en la primera posición del índice, ya que queremos mover el elemento más pequeño hacia el lado izquierdo, por lo que estamos comparando si el elemento actual es más pequeño que los elementos en su lado izquierdo.
Tipos de clasificación
Los tipos de algoritmos que se utilizan para ordenar datos abarcan los siguientes conceptos o ideas en su enfoque para ordenar los datos:
- Comparación versus estrategias no basadas en comparación,
- Implementación iterativa versus recursiva,
- Paradigma de divide y vencerás (esto o aquello),
- Enfoque aleatorio.
Consideremos algunos ejemplos:
1. La ordenación por fusión utiliza un enfoque de divide y vencerás para ordenar elementos en una matriz.
2. La ordenación por inserción, la ordenación por burbuja es una ordenación basada en la comparación.
Cuando se ordenan los datos, resulta más fácil encontrar una solución óptima para problemas complejos. por ejemplo,
- Buscando un valor específico,
- Encontrar el valor mínimo o máximo,
- Prueba de singularidad y eliminación de duplicados,
- Contando cuántas veces ha aparecido un valor específico, etc.
Conclusión
En este artículo, hemos revisado la definición del tipo de inserción y su complejidad de tiempo y varios otros tipos de algoritmos de clasificación basados en su enfoque. El estudio de varios algoritmos de clasificación nos ayuda a identificar cuál es el más adecuado en determinadas circunstancias o casos de uso que nos ayudan a clasificar los datos a un ritmo más rápido.
Artículos recomendados
Esta es una guía para la ordenación por inserción en JavaScript. Aquí discutimos qué es el tipo de inserción en javascript y sus tipos con un ejemplo. También puede consultar los siguientes artículos para obtener más información:
- Patrones en JavaScript
- Declaración de caso en JavaScript
- Declaraciones condicionales en JavaScript
- Objetos JavaScript
- Diferentes tipos de bucles con sus ventajas