Ordenamiento por inserción

El ordenamiento por inserción (Insertion Sort), también conocido generalmente como ordenamiento por inserción directa, es un algoritmo eficaz para ordenar una pequeña cantidad de elementos.

El ordenamiento por inserción es uno de los métodos de ordenamiento más simples. Su idea básica es insertar un registro en la tabla ordenada ya existente, obteniendo así una nueva tabla ordenada con un registro más.

En su proceso de implementación se usa un bucle doble: el bucle externo recorre todos los elementos excepto el primero, y el bucle interno busca la posición de inserción en la parte ordenada situada delante del elemento actual y realiza el desplazamiento.

Principio de funcionamiento

La idea central del ordenamiento por inserción es"construir una secuencia ordenada". Divide lógicamente el array (o lista) a ordenar en dos partes:

  1. Parte ordenada: inicialmente, normalmente se considera que el primer elemento del array es por sí mismo una secuencia ordenada.
  2. Parte no ordenada: desde el segundo elemento hasta el último elemento.

El algoritmoinserta repetidamente el primer elemento de la parte no ordenada en la posición correcta de la parte ordenada, hasta que la parte no ordenada quede vacía; así todo el array queda ordenado.

Descripción de aplicabilidad

La complejidad temporal promedio del ordenamiento por inserción también esO(n^2), la complejidad espacial es de orden constanteO(1), y la complejidad temporal concreta también está relacionada con el grado de orden del array.

En el ordenamiento por inserción, cuando el array a ordenar ya está ordenado, se da el mejor caso; solo basta con comparar el número actual con el anterior, y en total se necesitan compararN-1veces, la complejidad temporal esO(N). El peor caso ocurre cuando el array a ordenar está en orden inverso; en este momento se necesitan la mayor cantidad de comparaciones, y el peor caso esO(n^2)。

Ilustración del proceso

Supongamos que los primerosn-1(donden>=2) números ya están ordenados; ahora elnnúmero se inserta en la secuencia ya ordenada, luego encuentra su posición adecuada, de modo que la secuencia tras insertar el enésimo número también quede ordenada.

El proceso de insertar todos los elementos de esta manera hasta que toda la secuencia quede ordenada se denomina ordenamiento por inserción.

El proceso completo del ordenamiento por inserción de menor a mayor se muestra en la figura:

Primera iteración:Comienza la comparación desde el 6 en la segunda posición; al ser menor que el 7 anterior, intercambian posiciones.

Segunda iteración:El 9 en la tercera posición es mayor que el 7 de la posición anterior; no es necesario intercambiar posiciones.

Tercera iteración:El 3 en la cuarta posición es menor que el 9 de la posición anterior; intercambian posiciones y se compara sucesivamente hacia adelante.

Cuarta iteración:El 1 en la quinta posición es menor que el 9 de la posición anterior; intercambian posiciones y se compara sucesivamente hacia adelante.

......

Así se compara sucesivamente hasta el último elemento.

Código de ejemplo en Java

Descarga del paquete del código fuente:Download

Código parcial:

Código del archivo InsertionSort.java:

package ejemplo;

/**
* Ordenamiento por inserción
 */
public class InsertionSort {
    // Código principal --- inicio
    public static void sort(Comparable[] arr){

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // Buscar la posición de inserción adecuada para el elemento arr[i]
           for( int j = i ; j > 0 ; j -- )
                if( arr[j].compareTo( arr[j-1] ) < 0 )
                    swap( arr, j , j-1 );
                else
                    break;
        }
    }
    // Código principal --- fin
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {

        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        InsertionSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }

}

Implementación del algoritmo y análisis del código

Una vez entendido el principio, veamos la implementación concreta del código. Aquí se ofrecen versiones en Python y Java, dos lenguajes comunes.

Implementación en Python

Ejemplo

def insertion_sort(arr):
    """
Implementación del algoritmo de ordenamiento por inserción (ascendente)
:param arr: la lista a ordenar
:return: la lista ordenada (modifica in situ y también la devuelve)
    """
    # Recorrer desde el segundo elemento hasta el último (índice 1 a n-1)
    for i in range(1, len(arr)):
        current_value = arr[i]  # El elemento actual a insertar, primero se 'toma en la mano'
        j = i - 1               # j apunta al último elemento de la secuencia ordenada
       
        # Bucle interno: buscar la posición de inserción para current_value en la parte ordenada arr[0..i-1]
        # Condición 1: j >= 0 para asegurar no salir antes del inicio de la lista
        # Condición 2: arr[j] > current_value indica que el elemento comparado es mayor que el 'de la mano', por lo que debe desplazarse hacia atrás
        while j >= 0 and arr[j] > current_value:
            arr[j + 1] = arr[j]  # Mover el elemento mayor una posición hacia atrás para dejar un hueco
            j -= 1               # Continuar comparando el siguiente elemento hacia la izquierda
       
        # Al terminar el bucle, se ha encontrado la posición de inserción (j+1)
        # En este momento arr[j] <= current_value o j == -1
        arr[j + 1] = current_value  # Insertar el elemento 'de la mano' en la posición correcta
   
    return arr


# Código de prueba
if __name__ == "__main__":
    # Datos de prueba
    test_data = [64, 34, 25, 12, 22, 11, 90]
    print("Antes de ordenar:", test_data)
   
    sorted_data = insertion_sort(test_data.copy())  # Ordenar con una copia para no afectar los datos originales
    print("Después de ordenar:", sorted_data)
   
    # Otra prueba: datos casi ordenados
    nearly_sorted_data = [1, 3, 2, 4, 6, 5, 8, 7]
    print("\n"Datos casi ordenados antes de ordenar:", nearly_sorted_data)
    print("Datos casi ordenados después de ordenar:", insertion_sort(nearly_sorted_data.copy()))

Implementación en Java

Ejemplo

public class InsertionSort {
   
    public static void insertionSort(int[] arr) {
        // Recorrer desde el segundo elemento hasta el último (índice 1 a n-1)
        for (int i = 1; i < arr.length; i++) {
            int currentValue = arr[i]; // El elemento actual a insertar
            int j = i - 1;             // j apunta al último elemento de la secuencia ordenada
           
            // Bucle interno: buscar la posición de inserción y mover elementos
            while (j >= 0 && arr[j] > currentValue) {
                arr[j + 1] = arr[j]; // Desplazar el elemento hacia atrás
                j--;
            }
           
            // Insertar el elemento actual en la posición correcta
            arr[j + 1] = currentValue;
        }
    }
   
    // Método sobrecargado que permite ordenar una parte de un array de enteros
    public static void insertionSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int currentValue = arr[i];
            int j = i - 1;
           
            while (j >= left && arr[j] > currentValue) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = currentValue;
        }
    }
   
    public static void main(String[] args) {
        // Datos de prueba
        int[] testData = {64, 34, 25, 12, 22, 11, 90};
        System.out.print("Antes de ordenar: ");
        printArray(testData);
       
        int[] dataToSort = testData.clone(); // Usar una copia
        insertionSort(dataToSort);
        System.out.print("Después de ordenar: ");
        printArray(dataToSort);
    }
   
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Análisis de las características del algoritmo

Conocer el rendimiento y los escenarios de aplicación de un algoritmo es fundamental. Las características del ordenamiento por inserción se pueden resumir de la siguiente manera:

Característica Descripción Explicación
Complejidad temporal Casos promedio y peor: $O(n^2)$ Se necesitan bucles anidados para comparar y mover elementos. Para n elementos, en el peor caso (completamente en orden inverso) se requieren aproximadamente $\frac{n(n-1)}{2}$ comparaciones y movimientos.
Mejor caso：$O(n)$ Cuando el array de entrada ya está casi ordenado, el bucle interno se ejecuta poco o sale inmediatamente; solo se necesitan n-1 comparaciones.
Complejidad espacial $O(1)$ SíOrdenamiento in situalgoritmo que solo requiere espacio adicional de orden constante (comocurrent_value, jy otras variables).
Estabilidad Estable Cuando dos elementos son iguales, su orden relativo se conserva después de la ordenación. Porque el algoritmo solo al encontrar un valormayor queel valor actual, mueve el elemento.
Escenarios de aplicación 1. Datos a pequeña escala
2. Datos casi ordenados
3. Como subproceso de algoritmos de ordenamiento avanzados (como ordenamiento rápido, ordenamiento por combinación)		 En estos casos, su lógica simple y su bajo costo constante pueden hacer que su rendimiento sea mejor que el de algoritmos más complejos de $O(n \log n)$.

Derivación de la fórmula de complejidad temporal (peor caso)

En el peor caso (array completamente en orden inverso):

  • El primer elemento (índice 0) se inserta con 0 comparaciones.
  • El segundo elemento (índice 1) se inserta con 1 comparación y 1 movimiento.
  • El tercer elemento (índice 2) se inserta con 2 comparaciones y 2 movimientos.
  • ...
  • El enésimo elemento (índice n-1) se inserta con n-1 comparaciones y n-1 movimientos.

El número total de comparaciones y movimientos es: $0 + 1 + 2 + ... + (n-1) = \frac{n(n-1)}{2}$

Por lo tanto, la complejidad temporal es $O(n^2)$.

Más ejemplos de código

Otras extensiones