Ordenar y buscar en C: qsort, bsearch y búsqueda binaria

Ordenar y buscar en C con las funciones de la biblioteca estándar: qsort para ordenar arrays de números o de estructuras por varios campos, la forma correcta de escribir la función de comparación, bsearch para buscar en un array ordenado y una búsqueda binaria propia sin los errores clásicos.

Ordenar números con qsort

qsort, de <stdlib.h>, ordena un array de cualquier tipo. Recibe el array, cuántos elementos tiene, cuánto mide cada uno y una función que compara dos elementos y devuelve un número negativo, cero o positivo:

#include <stdio.h>
#include <stdlib.h>

static int ascendente(const void *a, const void *b)
{
    int x = *(const int *) a, y = *(const int *) b;
    return (x > y) - (x < y);
}

static int descendente(const void *a, const void *b)
{
    return ascendente(b, a);
}

int main(void)
{
    int v[] = {42, -7, 2147483647, 0, -2147483647, 15};
    size_t n = sizeof v / sizeof v[0];

    qsort(v, n, sizeof v[0], ascendente);
    for (size_t i = 0; i < n; i++) printf("%d ", v[i]);
    printf("\n");

    qsort(v, n, sizeof v[0], descendente);
    for (size_t i = 0; i < n; i++) printf("%d ", v[i]);
    printf("\n");
    return 0;
}

salida-2147483647 -7 0 15 42 2147483647 
2147483647 42 15 0 -7 -2147483647 

La comparación (x > y) - (x < y) devuelve -1, 0 o 1 sin riesgo. El atajo que aparece en muchos tutoriales, return x - y;, se desborda en cuanto los números son grandes y de signo contrario (como los extremos de este array) y ordena mal, además de ser comportamiento indefinido. Para el orden inverso basta con intercambiar los argumentos.

Ordenar estructuras por varios campos

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char nombre[24];
    char ciudad[16];
    int edad;
} Persona;

static int por_ciudad_y_edad(const void *a, const void *b)
{
    const Persona *x = a, *y = b;
    int c = strcmp(x->ciudad, y->ciudad);
    if (c != 0) return c;
    return (x->edad > y->edad) - (x->edad < y->edad);
}

int main(void)
{
    Persona gente[] = {
        {"Lucía", "Quito", 34}, {"Andrés", "Lima", 28}, {"Marta", "Quito", 22},
        {"Jorge", "Lima", 41}, {"Sofía", "Bogotá", 30},
    };
    size_t n = sizeof gente / sizeof gente[0];
    qsort(gente, n, sizeof gente[0], por_ciudad_y_edad);
    for (size_t i = 0; i < n; i++) {
        printf("%-7s %-7s %d\n", gente[i].ciudad, gente[i].nombre, gente[i].edad);
    }
    return 0;
}

salidaBogotá Sofía  30
Lima    Andrés 28
Lima    Jorge   41
Quito   Marta   22
Quito   Lucía  34

Para ordenar por varios criterios, la función compara el primero y solo si empatan pasa al segundo. Un detalle: strcmp compara bytes, así que «Bogotá» va antes que «Lima» por la B, pero con palabras que empiezan por una vocal con tilde el orden no sería el del diccionario (para eso existe strcoll con un locale en español). Y qsort no es estable: si dos elementos son iguales según la comparación, su orden final no está garantizado. Si importa, añade un último criterio de desempate.

Buscar en un array ordenado con bsearch

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    const char *codigo;
    const char *pais;
} Prefijo;

static int por_codigo(const void *a, const void *b)
{
    return strcmp(((const Prefijo *) a)->codigo, ((const Prefijo *) b)->codigo);
}

int main(void)
{
    Prefijo prefijos[] = {
        {"+34", "España"}, {"+52", "México"}, {"+51", "Perú"},
        {"+57", "Colombia"}, {"+54", "Argentina"}, {"+56", "Chile"},
    };
    size_t n = sizeof prefijos / sizeof prefijos[0];
    qsort(prefijos, n, sizeof prefijos[0], por_codigo);

    const char *buscados[] = {"+57", "+1", "+34"};
    for (int i = 0; i < 3; i++) {
        Prefijo clave = {.codigo = buscados[i]};
        const Prefijo *p = bsearch(&clave, prefijos, n, sizeof prefijos[0], por_codigo);
        printf("%-4s %s\n", buscados[i], p != nullptr ? p->pais : "(no está)");
    }
    return 0;
}

salida+57  Colombia
+1   (no está)
+34  España

bsearch hace una búsqueda binaria: mira el elemento del medio y descarta la mitad en la que no puede estar, así que en un millón de elementos encuentra cualquiera en unos 20 pasos. A cambio, el array tiene que estar ordenado con la misma función de comparación. La clave que se busca es un elemento del mismo tipo con solo el campo que importa relleno. Devuelve un puntero al elemento encontrado o nullptr.

Escribir tu propia búsqueda binaria

#include <stdio.h>

/* Devuelve la posición de x en v (ordenado), o -1. */
long buscar(const int *v, size_t n, int x)
{
    size_t izq = 0, der = n;
    while (izq < der) {
        size_t medio = izq + (der - izq) / 2;
        if (v[medio] < x) izq = medio + 1;
        else if (v[medio] > x) der = medio;
        else return (long) medio;
    }
    return -1;
}

int main(void)
{
    int v[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    printf("%ld %ld %ld %ld\n", buscar(v, 10, 13), buscar(v, 10, 2), buscar(v, 10, 29), buscar(v, 10, 4));
    return 0;
}

salida5 0 9 -1

Fíjate en izq + (der - izq) / 2 en lugar del obvio (izq + der) / 2. La versión obvia se desborda cuando los índices son muy grandes: fue un fallo real que estuvo casi diez años en la búsqueda binaria de la biblioteca de Java, hasta 2006. El intervalo semiabierto (der apunta una posición más allá) evita los errores de uno típicos de este algoritmo.

Todo el código de esta página se compiló con GCC 15.3 (C23, -Wall -Wextra, sin avisos) y se ejecutó en Linux, en un contenedor limpio sin acceso a la red, antes de publicarla; las salidas están copiadas de esa ejecución.