Ordenamiento clásico en C

Insertion Sort ordena construyendo una sublista ordenada desde el inicio del array y ubicando cada nuevo elemento en su posición correcta. Es intuitivo, similar a acomodar cartas en la mano, y funciona muy bien cuando los datos ya están casi ordenados.

4.1 Idea general del algoritmo

Partimos de la premisa de que el primer elemento ya está ordenado. Luego avanzamos elemento por elemento, insertando cada valor en la posición adecuada dentro de la porción izquierda que ya está ordenada.

4.2 Concepto de sublista ordenada

Despues de cada iteración, la sección arr[0..i] queda ordenada. El resto del array permanece pendiente de ordenar.

4.3 Inserción en su posición correcta

Para insertar un elemento, primero buscamos dónde debe ubicarse y luego desplazamos a la derecha los elementos mayores para abrir un hueco.

4.4 Búsqueda de la posición de inserción

Comparamos el elemento actual con los de la sublista ordenada moviéndonos hacia la izquierda. Cuando encontramos uno menor o igual, sabemos que la posición es inmediatamente después.

4.5 Desplazamiento de elementos

Cada elemento mayor al valor que insertamos se mueve una posición a la derecha. Esto preserva el orden de los elementos iguales, por lo que el algoritmo es estable.

4.6 Implementación en C

Versión clásica para enteros. Usa un bucle externo que recorre cada elemento y un bucle interno que desplaza hasta encontrar la posición correcta.

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

Explicación línea por línea:

for (int i = 1; i < n; i++): recorre elementos desde el segundo, que es el primero que puede desplazarse.
int actual = arr[i];: guarda el valor que queremos insertar en la sublista ordenada.
int j = i - 1;: arranca la comparación desde el elemento previo dentro de la sublista.
while (j >= 0 && arr[j] > actual): busca hacia la izquierda hasta hallar un elemento menor o igual; mientras sea mayor, se desplaza.
arr[j + 1] = arr[j];: mueve el elemento mayor una posición a la derecha para hacer lugar.
j--;: avanza el índice hacia la izquierda para seguir comparando.
arr[j + 1] = actual;: coloca el valor original en la posición vaciada, que es su lugar correcto.

4.7 Complejidad temporal y espacial

Tiempo: O(n^2) en el peor caso (lista inversa); O(n) en el mejor caso cuando la lista ya está ordenada.
Memoria: O(1) adicional; trabaja in-place.
Estabilidad: estable por el desplazamiento ordenado hacia la derecha.

4.8 Ventajas y desventajas

Ventajas: excelente rendimiento en listas pequeñas o casi ordenadas; estable; implementación breve y clara.
Desventajas: su complejidad cuadrática lo limita para listas grandes; el desplazamiento puede ser costoso cuando los datos están muy desordenados.

4.9 Casos donde Insertion Sort es excelente

Datos casi ordenados, donde el número de desplazamientos es mínimo.
Listas pequeñas, por ejemplo, tramos cortos dentro de un algoritmo híbrido.
Situaciones donde la estabilidad es importante y el tamaño de la entrada es acotado.

Insertion Sort suele usarse dentro de implementaciones híbridas: algoritmos más rápidos como quicksort delegan a Insertion Sort cuando el subarray es pequeño para aprovechar su simplicidad.

4.10 Archivos para un proyecto en CLion

Para practicar Insertion Sort en un proyecto limpio de CLion, usa estos archivos:

swap.h y swap.c: función de intercambio reutilizable.
utils.h y utils.c: impresión de arrays para validar resultados.
insertion_sort.c: implementación del algoritmo y su prototipo.
main.c: prepara datos de prueba, llama a insertion_sort y muestra antes/después.

Códigos completos:

/* swap.h */
void swap(int *a, int *b);

/* swap.c */
#include "swap.h"

void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

/* utils.h */
void imprimir_array(const int *arr, int n);

/* utils.c */
#include <stdio.h>
#include "utils.h"

void imprimir_array(const int *arr, int n) {
  printf("[");
  for (int i = 0; i < n; i++) {
    printf("%d", arr[i]);
    if (i + 1 < n) {
      printf(", ");
    }
  }
  printf("]\n");
}

/* insertion_sort.c */
void insertion_sort(int *arr, int n) {
  for (int i = 1; i < n; i++) {
    int actual = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > actual) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = actual;
  }
}

/* main.c */
#include <stdio.h>
#include "swap.h"
#include "utils.h"

void insertion_sort(int *arr, int n); /* prototipo */

int main(void) {
  int datos[] = {7, 4, 5, 2, 9};
  int n = sizeof(datos) / sizeof(datos[0]);

  printf("Antes: ");
  imprimir_array(datos, n);

  insertion_sort(datos, n);

  printf("Despues: ");
  imprimir_array(datos, n);
  return 0;
}

Retornar

4 - Insertion Sort