Introducción a la ordenación por inserción en Java
Si eres un programador, ya debes haber escuchado sobre ordenar mucho. La ordenación consiste básicamente en organizar los elementos en orden ascendente o descendente. Hay tantos algoritmos de clasificación disponibles para ordenar los elementos y cada algoritmo tiene diferentes formas de ordenar, diferente complejidad. Por lo tanto, depende del escenario específico y la cantidad de elementos en cuanto a qué algoritmo debe usarse. La inserción es también uno de los algoritmos de clasificación comúnmente utilizados que tiene la complejidad de O (n 2) en general y se realiza como si clasificamos las cartas en nuestras manos. En este tema, vamos a aprender sobre el orden de inserción en Java.
¿Cómo funciona la ordenación por inserción en Java?
Vamos a entender el funcionamiento de la inserción mediante un ejemplo. Supongamos que hay una matriz con el nombre arr que tiene los elementos mencionados a continuación:
10 5 8 20 30 2 9 7
Paso 1: la ordenación por inserción comienza con el segundo elemento de la matriz, es decir, 5, considerando el primer elemento de la matriz clasificado en sí mismo. Ahora el elemento 5 se compara con 10 ya que 5 es menor que 10, por lo que 10 se mueve 1 posición hacia adelante y 5 se inserta antes.
Ahora la matriz resultante es:
5 10 8 20 30 2 9 7
Paso # 2 - Ahora el elemento arr (2), es decir, 8 se compara con el elemento arr (1), es decir 10. Como 8 es más pequeño que su elemento anterior 10, se desplaza un paso hacia adelante desde su posición y luego se en comparación con 5. Dado que 8 es mayor que 5, entonces se inserta después.
Entonces la matriz resultante es:
5 8 10 20 30 2 9 7
Paso # 3 - Ahora el elemento 20 se compara con 10 ya que es mayor que 10, permanece en su posición.
5 8 10 20 30 2 9 7
Paso 4: el elemento 30 se compara con 20, y dado que es mayor que 20, no se realizarán cambios y la matriz permanecerá como está. Ahora la matriz sería
5 8 10 20 30 2 9 7
Paso 5: el elemento 2 se compara con 30, ya que es más pequeño que 30, se desplaza una posición adelante y luego se compara con 20, 10, 8, 5, uno por uno y todos los elementos se desplazan a 1 posición adelante y 2 se inserta antes que 5.
La matriz resultante es:
2 5 8 10 20 30 9 7
Paso 6: el elemento 9 se compara con 30, ya que es menor que 30, se compara con 20, 10 uno por uno y el elemento se desplaza 1 posición hacia adelante y se inserta 9 antes de 10 y después de 8. La matriz resultante es:
2 5 8 9 10 20 30 7
Paso 7: el elemento 7 se compara con 30, y dado que es menor que 30, se compara con 30, 20, 10, 9, 8 y todos los elementos se desplazan 1 posición uno por uno y se inserta 7 antes de 8 La matriz resultante se convertiría en:
2 5 7 8 9 10 20 30
De esta manera, todos los elementos de la matriz se ordenan utilizando el orden de inserción, comenzando la comparación con el elemento anterior.
Ejemplos para implementar el orden de inserción en Java
Insertion Sort en Java es un algoritmo de clasificación simple adecuado para todos los conjuntos de datos pequeños.
public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)
Salida:
12 15 18 21 23 52 61
Explicación:
En el programa anterior de Insertion Sort, la función insertionSort () se usa para ordenar los elementos de la matriz original. La ordenación comienza desde el segundo elemento ya que el primer elemento considera que está ordenado en sí mismo. Entonces el ciclo de 'j' comienza desde el índice 1 de la matriz. 'i' es la variable que realiza un seguimiento del índice justo antes de la 'j' para comparar el valor '. clave 'es la variable que contiene el valor del elemento actual que se debe organizar en posición ordenada. El bucle while () se ejecuta si el valor actual es menor que el valor situado más a la izquierda, de modo que se pueda procesar el desplazamiento de los elementos y, al final, se pueda realizar la inserción del elemento actual en la posición correcta. La función printArray () se utiliza para imprimir finalmente la matriz ordenada.
1. Mejor caso
En el orden de inserción, el mejor caso sería cuando todos los elementos de la matriz ya estén ordenados. Entonces, cuando cualquier elemento se compara con su elemento más a la izquierda, siempre es mayor y, por lo tanto, no se procesará el desplazamiento ni la inserción de elementos. En este caso, la mejor complejidad del caso sería lineal, es decir, O (n).
2. Peor caso
En el código de clasificación de inserción anterior, el peor de los casos sería cuando la matriz está en orden inverso, por lo que cada vez que se compara el elemento con su elemento más a la izquierda, siempre es más pequeño y luego se compara con todos los elementos que se producen y cambian y se realiza la inserción. En este caso, la complejidad del orden de inserción es O (n 2).
3. Caso promedio
Incluso en un caso promedio, la ordenación por inserción tiene una complejidad O (n 2) en la que algunos elementos no requieren desplazamiento mientras que algunos elementos se desplazan desde sus posiciones y se realiza la inserción en la posición correcta.
4. Mejor uso
La ordenación por inserción es mejor cuando el tamaño de una matriz no es muy grande o solo se necesita ordenar una pequeña cantidad de elementos en los que se ordenan casi todos los elementos y solo se necesitan algunos cambios. La ordenación por inserción es uno de los algoritmos más rápidos para una matriz de tamaño pequeño, incluso más rápido que la ordenación rápida. De hecho, quicksort utiliza la ordenación por inserción al ordenar sus pequeñas partes de la matriz.
Conclusión
La explicación anterior muestra claramente el funcionamiento y la implementación de Insertion Sort en Java. En otros lenguajes de programación también, la lógica para realizar la ordenación por inserción sigue siendo la misma solo que cambia la sintaxis. Antes de implementar cualquier algoritmo de clasificación, es muy importante hacer un análisis del escenario en el que la clasificación debe realizarse, ya que no todos los algoritmos de clasificación se ajustan a todos los escenarios.
Artículos recomendados
Esta es una guía para la ordenación por inserción en Java. Aquí discutimos cómo funciona la ordenación por inserción en Java con ejemplos para implementar la ordenación por inserción en Java. También puede echar un vistazo a los siguientes artículos para obtener más información:
- Raíz cuadrada en Java
- BorderLayout en Java
- Número inverso en Java
- StringBuffer en Java
- Raíz cuadrada en PHP
- Raíz cuadrada en JavaScript
- Guía de los 6 mejores algoritmos de clasificación en Python