Algoritmo Insertion Sort en Java: Ejemplo Claro y Guía Paso a Paso

¿Qué es el Algoritmo Insertion Sort?

Insertion sort (ordenamiento por inserción) es una técnica de ordenamiento sencilla ideal para conjuntos de datos pequeños o casi ordenados. En cada iteración, el algoritmo extrae un elemento, lo compara con los elementos precedentes y lo coloca en su posición correcta.

Insertion sort opera en tiempo O(n²) en el peor y caso promedio, pero alcanza rendimiento lineal cuando el array ya está ordenado. Es un ordenamiento in-place, estable y que requiere solo espacio extra constante.

Proceso del Algoritmo Insertion Sort

Aquí hay una representación visual del flujo de trabajo de insertion sort:

Proceso del Algoritmo Insertion Sort

Programa Java de Ejemplo para Ordenar un Array usando Insertion Sort:

package com.guru99;
public class InsertionSortExample {
    public static void main(String a[]) {
        int[] myArray = {860, 8, 200, 9};
        System.out.println("Antes de Insertion Sort");
        printArray(myArray);
        insertionSort(myArray); // ordenando array usando insertion sort
        System.out.println("Después de Insertion Sort");
        printArray(myArray);
    }

    public static void insertionSort(int arr[]) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            System.out.println("Pasada de Ordenamiento Número " + (i));
            int key = arr[i];
            int j = i - 1;
            while ((j > -1) && (arr[j] > key)) {
                System.out.println("Comparando " + key + " y " + arr[j]);
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
            System.out.println("Intercambiando Elementos: Nuevo Array Después del Intercambio");
            printArray(arr);
        }
    }

    static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

Salida del Código:

Antes de Insertion Sort
860 8 200 9
Pasada de Ordenamiento Número 1
Comparando 8 y 860
Intercambiando Elementos: Nuevo Array Después del Intercambio
8 860 200 9
Pasada de Ordenamiento Número 2
Comparando 200 y 860
Intercambiando Elementos: Nuevo Array Después del Intercambio
8 200 860 9
Pasada de Ordenamiento Número 3
Comparando 9 y 860
Comparando 9 y 200
Intercambiando Elementos: Nuevo Array Después del Intercambio
8 9 200 860
Después de Insertion Sort
8 9 200 860