Inserción binaria en C: ejercicio resuelto de ordenación

Método de inserción binaria en C

Si buscas inserción binaria en C ejercicio resuelto, aquí tienes una implementación completa con la idea clave: separar la búsqueda de posición y el desplazamiento de elementos.

Inserción binaria es una variante de inserción directa. Reduce comparaciones usando búsqueda binaria para encontrar dónde insertar, pero sigue necesitando mover elementos en el array.

Enunciado

Implementa inserción binaria para ordenar un array de enteros en orden ascendente.

Solución en C

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <stdio.h>

int posicion_insercion(const int a[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (a[mid] <= key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

void insercion_binaria(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int pos = posicion_insercion(a, 0, i - 1, key);

        for (int j = i - 1; j >= pos; j--) {
            a[j + 1] = a[j];
        }
        a[pos] = key;
    }
}

int main(void) {
    int a[] = {37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54, 54};
    int n = (int)(sizeof(a) / sizeof(a[0]));

    insercion_binaria(a, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

Resultado esperado

1

0 12 17 23 31 37 46 54 54 72 88 100

Errores frecuentes

  • Buscar posición en un rango incorrecto (0..i en lugar de 0..i-1).
  • Olvidar desplazar elementos antes de insertar key.
  • Usar una condición errónea con repetidos y perder estabilidad.
  • Pensar que pasa a O(n log n): el desplazamiento sigue siendo lineal.

Aplicación práctica

Este ejercicio sirve para:

  • entender bien la diferencia entre coste de comparación y coste de movimiento,
  • practicar implementación de búsqueda binaria sobre un prefijo ordenado,
  • preparar entrevistas donde te piden optimizar inserción directa sin cambiar estructura.

Siguiente ejercicio recomendado

Práctica guiada y siguiente paso

Si quieres una ruta completa con progresión real de dificultad:

FAQ

¿Inserción binaria en C es más rápida que inserción directa?

Reduce comparaciones gracias a la búsqueda binaria, pero sigue desplazando elementos, así que no elimina el coste cuadrático en peor caso.

¿Cuál es su complejidad temporal?

En promedio y peor caso se mantiene en O(n²) por los desplazamientos. La búsqueda de posición cuesta O(log n), pero no domina el total.

¿Cuándo merece la pena usarla en práctica?

Cuando quieres mejorar inserción directa en arrays pequeños o medianos y practicar técnicas de búsqueda y ordenación en un mismo ejercicio.