Sorteo de inserción en JavaScript
El algoritmo de clasificación de inserción es muy útil en aquellos casos en los que tenemos un número menor de elementos en una lista o donde la mayor parte de la lista ya está ordenada y menos elementos están fuera de lugar.
Cómo funciona la clasificación de inserción
Consideremos un ejemplo para comprender mejor la lógica detrás del tipo de inserción. Supongamos que tenemos una matriz sin clasificar de 6 elementos y tenemos que clasificarlos usando el orden de inserción:
Ahora para ordenar la matriz anterior, iteraremos la matriz del índice 1 al último índice. Inicialmente, asumimos que el índice 0 de la matriz está ordenado, a partir de entonces haremos una comparación del elemento actual con su elemento anterior. Si el elemento actual es menor que el elemento anterior, entonces cambiaremos sus posiciones.
Primer paso
En el primer paso, compararemos el índice 1 con el índice 0, el valor del primer índice '47' es mayor que 0º valor del índice, por lo que no habrá cambios en el primer paso (los elementos no cambiarían):
Segundo paso
Ahora, en el segundo paso, asumiremos que los dos primeros elementos están ordenados, por lo que el cursor estará en el índice 2, y compararemos el índice 2 con sus elementos anteriores:
Dado que '25' es más pequeño que '47', intercambio '25' y '47'. A continuación, '25' también se compara con el valor del índice 0. '25' es mayor que '15', por lo que no se cambiaría.
La matriz después del segundo paso se actualizará como:
Tercer paso
Aquí en el tercer paso, consideramos que los tres primeros valores están ordenados y el cursor estará en el tercer índice. Entonces, compararemos el tercer índice con sus valores anteriores:
En el índice 3, '55' se compara con cada elemento uno por uno, pero es mayor que todos sus elementos anteriores, por lo que no habrá cambios en la posición de los elementos de matriz.
Cuarto paso
Ahora estamos en el índice 4, donde tenemos un valor '20' y tenemos que compararlo con todos los elementos anteriores de la matriz:
Dado que '20' es menor que '25', '47' y '55', se insertará en el primer índice, y '25', '47' y '55' se moverán al lado derecho por un índice (I+1 índice) de sus índices actuales.
La matriz actualizada será:
Quinto paso
Ahora estamos en el índice 5 donde el valor actual es '10', que es el más pequeño entre todos los valores de la matriz, por lo que se insertará en el índice 0.
De esta manera, toda la matriz se clasificará utilizando la clasificación de inserción:
Como hemos terminado con la parte conceptual del orden de inserción, ahora implementaremos este concepto en JavaScript.
Implementación del orden de inserción en JavaScript
El código para implementar el tipo de inserción en JavaScript es el siguiente:
función insertion_sort (input_array, array_length)
Deje que yo, pivot_value, j;
para (i = 1; i = 0 && input_array [j]> pivot_value)
input_array [j + 1] = input_array [j];
j = j - 1;
input_array [j + 1] = pivot_value;
return input_array;
Let input_array = [15,47,25,55,20,10];
dejar array_length = input_array.longitud;
insertion_sort (input_array, array_length);
consola.log ("matriz clasificada final:", input_array);
En el código anterior, creamos una función "tipo de inserción"Y lo pasé la matriz de entrada y la longitud de la matriz. Luego iteramos el bucle hasta la longitud de la matriz.
Dentro del bucle, seleccionamos el 'pivot_value = input_array [i]"Como valor de pivote para hacer una comparación del elemento actual con sus elementos anteriores y establecer"J = I-1"Que representa el último elemento de nuestra matriz ordenada.
Aquí en cada iteración, el elemento actual se asigna al valor de pivote y el valor de pivote se considerará como el primer elemento de la matriz no organizada en cada paso.
Utilizamos un bucle de tiempo para clasificar los elementos de matriz, aquí en este bucle comparamos el elemento actual con sus elementos anteriores. Si el elemento actual es menor que cualquiera de los elementos anteriores, y encontramos la posición apropiada para insertar ese elemento en la matriz ordenada, entonces insertamos ese elemento en la posición apropiada y movemos los otros elementos un lugar al lado derecho. Y todo el fenómeno se repite para cada paso hasta que la matriz se ordene por completo.
Producción
Finalmente, llamamos al "tipo de inserción"Función e imprima la matriz ordenada en la consola del navegador utilizando el"consola.registro" método. La salida del algoritmo de clasificación de inserción será:
Conclusión
La clasificación de inserción es un algoritmo de clasificación que clasifica un elemento a la vez. Inserta el elemento en la posición apropiada uno por uno para crear una matriz ordenada. Proporciona resultados eficientes si el número de elementos de matriz es pequeño y la mayoría de los elementos de la matriz ya están ordenados.
En este artículo, consideramos un ejemplo para descubrir la lógica del orden de inserción, discutimos el funcionamiento del algoritmo de clasificación de inserción con respecto a cada paso y presentar la matriz actualizada después de cada paso. Y finalmente, una vez que percibimos la idea detrás del tipo de inserción, la implementamos en JavaScript.