Algoritmos de Ordenamiento

Insertion Sort (Inserción) Paso a Paso

Inserción adaptativa, listas semi-ordenadas y O(N) mejor caso en C, Java, JavaScript y Python.

1. Mecánica de Inserción Adaptativa

Insertion Sort funciona de forma similar a ordenar cartas en la mano: toma un elemento y lo desplaza hacia la izquierda hasta insertarlo en su posición correcta.

ANÁLISIS ALGORÍTMICO

Mejor Caso (Array Casi Ordenado)O(N) lineal

Peor Caso (Invertido)O(N²)

EstabilidadEstable (preserva orden)

2. C: Insertion Sort

Ideal para conjuntos pequeños de datos o vectores casi ordenados.

insertion.c

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

3. Java: Insertion Sort

Utilizado internamente como subrutina en algoritmos híbridos de ordenamiento (Timsort / Dual-Pivot Quicksort) para particiones pequeñas.

InsertionSort.java

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; j--;
        }
        arr[j + 1] = key;
    }
}

4. JavaScript: Insertion Sort

Procesamiento eficiente de desplazamiento de claves mediante bucle `while`.

insertion.js

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

5. Python: Insertion Sort

Sintaxis directa con bucle `while` decrementando el índice `j`.

insertion.py

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

6. Inspector de Inserción de Clave

Array: [12, 11, 13]

Clave key=11 ➔ Desplaza 12 a pos 1 ➔ Inserta 11 en pos 0 ➔ [11, 12, 13]