Algoritmo de ordenación por inserción en Java con ejemplo de programa

Por: james hartman james hartman
Hours Actualizado

⚡ Resumen inteligente

Ordenación por inserción en Java Construye una sección ordenada de una matriz elemento por elemento, desplazando los valores más grandes hacia la derecha hasta que cada clave se ubica en su posición correcta, lo que lo hace ideal para conjuntos de datos pequeños.

  • 🔘 Definición: La ordenación por inserción elimina un elemento y lo inserta en su lugar correcto dentro de la parte ordenada.
  • ☑️ Proceso: En cada pasada, se compara la clave con valores anteriores y se desplazan los valores mayores una posición a la derecha.
  • ✅ Programa: El Java El ejemplo ordena {860, 8, 200, 9} e imprime cada comparación e intercambio.
  • 🧪 Complejidad: El mejor caso se ejecuta en tiempo O(n), mientras que los casos promedio y peor alcanzan O(n²).
  • 🛠️ Memoria: La ordenación se realiza in situ, por lo que el espacio auxiliar se mantiene en O(1) para cualquier tamaño de matriz.
  • 📊 Comportamiento: El algoritmo es estable y adaptativo, por lo que los arreglos casi ordenados terminan después de muy pocos desplazamientos.
Descubre más

Algoritmo de ordenación por inserción en Java

¿Qué es el algoritmo de clasificación por inserción?

La clasificación por inserción es un algoritmo de clasificación simple adecuado para conjuntos de datos pequeños. Durante cada iteración, el algoritmo:

  • Elimina un elemento de una matriz.
  • Lo compara con el valor más grande del matriz.
  • Mueve el elemento a su ubicación correcta.

Este comportamiento refleja la forma en que un jugador de cartas organiza su mano: cada nueva carta se toma y se desplaza hacia la izquierda, pasando por encima de cada carta más grande, hasta que se coloca en el lugar correcto. Dado que todo el desplazamiento se produce dentro del arreglo original, el algoritmo de ordenación por inserción es estable y no requiere desplazamientos.

Pertenece a la misma familia de juegos fáciles de usar para principiantes. Java rutinas de clasificación como ordenamiento de burbujaSin embargo, normalmente realiza muchas menos escrituras en datos que ya están parcialmente ordenados.

Proceso del algoritmo de clasificación por inserción

Así es como funciona gráficamente el proceso del algoritmo de clasificación por inserción:

animado trace del algoritmo de ordenación por inserción reordenando una lista no ordenada
Proceso del algoritmo de clasificación por inserción

La animación repite los mismos tres pasos. Java El programa que se muestra a continuación se ejecuta. La tabla de prueba en seco tracesos pasos en el array de muestra {860, 8, 200, 9}, exactamente como el programa los imprime en tiempo de ejecución.

Pasó Elemento clave Comparaciones realizadas Matriz después del paso
1 8 8 contra 860 8 860 200 9
2 200 200 contra 860 8 200 860 9
3 9 9 contra 860, luego 9 contra 200 8 9 200 860

Nótese que el paso 3 requiere dos comparaciones porque la clave 9 tiene que pasar por dos valores mayores. Por lo tanto, el número de comparaciones aumenta en función de cuán desordenado esté el inicio de cada elemento.

Java Ejemplo de programa para ordenar una matriz usando el algoritmo de ordenación por inserción:

El programa que se muestra a continuación ordena el array {860, 8, 200, 9} e imprime un comentario en tiempo real, de modo que cada comparación y cada cambio de posición son visibles. Guárdelo como InsertionSortExample.java y compilarlo con cualquier versión de JDK 8 o posterior.

package com.guru99;
 
public class InsertionSortExample {
 
	
    public static void main(String a[])
    {    
        int[] myArray  = {860,8,200,9};  
        
        System.out.println("Before Insertion Sort");  
        
        printArray(myArray);
            
        insertionSort(myArray);//sorting array using insertion sort    
           
        System.out.println("After Insertion Sort");  
        
        printArray(myArray);   
    }    
 public static void insertionSort(int arr[]) 
	{  
        int n = arr.length;  
        
        for (int i = 1; i < n; i++)
        {   System.out.println("Sort Pass Number "+(i));
            int key = arr[i];  
            int j = i-1;  
            
            while ( (j > -1) && ( arr [j] > key ) ) 
            {  
            System.out.println("Comparing "+ key  + " and " + arr [j]); 
                arr [j+1] = arr [j];  
                j--;  
            }  
            arr[j+1] = key; 
            System.out.println("Swapping Elements: New Array After Swap");
            printArray(arr);
        }  
    }
 static void printArray(int[] array){
	    
	    for(int i=0; i < array.length; i++)
		{  
			System.out.print(array[i] + " ");  
		} 
	    System.out.println();
	    
	}
}

Al ejecutar la clase se produce el trace se muestra aquí. Cada Número de pase de ordenación La línea indica una iteración del bucle exterior, y la línea impresa después de cada intercambio muestra el arreglo tal como se encuentra en ese momento.

Code Salida:

Before Insertion Sort
860 8 200 9 
Sort Pass Number 1
Comparing 8 and 860
Swapping Elements: New Array After Swap
8 860 200 9 
Sort Pass Number 2
Comparing 200 and 860
Swapping Elements: New Array After Swap
8 200 860 9 
Sort Pass Number 3
Comparing 9 and 860
Comparing 9 and 200
Swapping Elements: New Array After Swap
8 9 200 860 
After Insertion Sort
8 9 200 860

ARTÍCULOS RELACIONADOS

Complejidad temporal y espacial del algoritmo de ordenación por inserción

El rendimiento del algoritmo de ordenación por inserción depende en gran medida del grado de ordenación que ya presente la entrada, razón por la cual el mejor y el peor caso difieren en un orden de magnitud completo.

Caso condición de entrada Complejidad de tiempo
mejor El array ya está ordenado, por lo que el bucle while interno nunca se ejecuta. O (n)
Normal Los elementos llegan en orden aleatorio. O (n²)
Peor El array está ordenado en orden inverso, por lo que cada clave se desplaza hacia el frente. O (n²)

El uso del espacio es mucho más sencillo. Solo los contadores i, j, n y key se crean y la matriz se reorganiza en el lugar, por lo que el espacio auxiliar es O(1) sin importar cuán grande crezca la entrada.

Debido a que el bucle interno se detiene tan pronto como encuentra un valor menor, el algoritmo de ordenación por inserción se describe como adaptativo: cuanto más se acerque la entrada al orden ordenado, más se aproximará el tiempo de ejecución a un valor lineal.

Ventajas y desventajas del algoritmo de ordenación por inserción

El algoritmo de ordenación por inserción se mantiene en las bibliotecas de producción a pesar de su promedio cuadrático, porque sus factores constantes son muy pequeños y su comportamiento es predecible.

Ventajas

  • Sencillo de escribir y fácil de tracy a mano, lo que lo hace adecuado para la enseñanza y las entrevistas.
  • Es estable, por lo que los registros que comparten una clave conservan su orden relativo original.
  • In situ, necesitando solo O(1) de memoria adicional más allá del array de entrada.
  • Adaptativo, alcanzando O(n) en datos que ya están casi ordenados.
  • En línea, lo que significa que puede ordenar una lista mientras siguen llegando nuevos elementos.

Desventajas

  • Su complejidad computacional cuadrática con entradas aleatorias o en orden inverso lo hace inadecuado para matrices grandes.
  • Cada desplazamiento escribe en la matriz, por lo que mueve más datos que el algoritmo de ordenación por selección.
  • Los algoritmos de ordenación por fusión y ordenación rápida lo superan con creces una vez que la entrada supera unas pocas docenas de elementos.

Una regla práctica es recurrir a la ordenación por inserción cuando el array es pequeño, cuando los datos están casi ordenados o cuando una ordenación por divide y vencerás ha reducido una partición a un puñado de elementos.

Ordenación por inserción vs. BubblOrdenación por selección vs. Ordenación por selección

Los tres algoritmos son algoritmos de ordenación por comparación cuadrática, pero difieren en estabilidad, en cómo reaccionan a las entradas ordenadas y en la cantidad de escrituras que realizan.

Criterios Tipo de inserción Bubble Ordenar Selección Ordenar
Mejores casos O (n) O(n) con un indicador de salida anticipada O (n²)
Caso promedio y peor caso O (n²) O (n²) O (n²)
Espacio extra O (1) O (1) O (1)
Estable Sí: Sí: No, en la versión estándar de la matriz
Adaptado Sí: Sí, cuando se utiliza la optimización de banderas. No
Escribe en el array Muchos cambios, pocos en datos ordenados Muchos intercambios Exactamente n-1 intercambios

La ordenación por selección gana cuando una escritura es costosa, porque realiza la menor cantidad de intercambios. La ordenación por inserción gana en casi todos los demás casos a esta escala, especialmente en datos parcialmente ordenados, razón por la cual las ordenaciones de biblioteca como la que se muestra a continuación... común Java ejercicios y el código interno del JDK cambia a este formato para particiones muy pequeñas.

Preguntas Frecuentes

El primer elemento por sí solo ya es un subconjunto ordenado de longitud uno. Comenzar en el índice 1 significa que el bucle siempre tiene algo con lo que comparar, por lo que la clave en la posición i se inserta en el bloque ordenado a su izquierda.

Los asistentes de IA pueden narrar una ejecución de prueba línea por línea, generar matrices de prueba adicionales y estimar el crecimiento de la complejidad asintótica (Big O) a partir del código fuente. Considere la explicación como una ayuda para el estudio y verifique las afirmaciones sobre complejidad con un libro de texto antes de citarlas.

Sí. Copiloto de GitHub Completa una ordenación de inserción estándar a partir de la firma o el comentario de un método. RevRevisa tú mismo las condiciones límite, porque los bucles generados a veces usan j >= 0 o j > -1 de forma inconsistente con el código circundante.

El algoritmo de ordenación por inserción binaria localiza el punto de inserción mediante una búsqueda binaria en lugar de un escaneo lineal, reduciendo las comparaciones por elemento de O(n) a O(log n). El trabajo de desplazamiento permanece sin cambios, por lo que la complejidad temporal total se mantiene en O(n²).

Sí. Una versión recursiva ordena los primeros n-1 elementos y luego inserta el último elemento en ese prefijo ordenado. Tiene la misma complejidad temporal que la iterativa, pero requiere un espacio de pila de O(n), por lo que en la práctica se prefiere la versión con bucle.

En parte. El algoritmo quicksort de doble pivote utilizado para tipos primitivos recurre a un algoritmo de ordenación por inserción en particiones muy pequeñas, y TimSort, utilizado para objetos, ordena secuencias cortas con un algoritmo de ordenación por inserción binaria antes de fusionarlas.

Los fallos frecuentes son comenzar el bucle exterior en 0, escribir arr[j] = key en lugar de arr[j+1] = key, y omitir la condición j > -1, que lanza ArrayIndexOutOfBoundsException cuando la clave pertenece a la posición cero.

Sí. Reemplace la prueba de mayor que con compareTo para un tipo Comparable, o con una llamada a Comparator. La lógica de desplazamiento no cambia y se conserva la estabilidad, lo cual es importante cuando los objetos comparten la misma clave de ordenación.

Resumir este post con: