Lección 7 · 7 de 20

qsort y bsearch con comparadores · C

Ordene un array de structs en C con qsort y una función comparadora, y busque en él con bsearch: los productos de una tienda por precio y por código.

C · qsort y bsearch con comparadores en DMarlon Studio: el código del ejemplo y su salida en la terminal

`qsort`, de stdlib.h, ordena cualquier array: recibe el array, cuántos elementos tiene, el tamaño de cada uno y un comparador. No sabe qué hay dentro; por eso el comparador recibe dos const void *, que se convierten al tipo real, aquí const Product *.

El comparador devuelve un número negativo si el primero va antes, cero si son iguales y positivo si va después. (x > y) - (x < y) da exactamente -1, 0 o 1. La tentación de escribir x - y falla con los double (al convertir a int, 0.5 se queda en 0) y con enteros muy grandes, que se desbordan.

by_price ordena de más barato a más caro. Para el orden contrario basta cambiar a por b en el comparador.

`bsearch` hace una búsqueda binaria: mira el centro y descarta la mitad en cada paso, así que encuentra un elemento entre un millón en unas 20 comparaciones. A cambio, el array tiene que estar ordenado por la misma clave que se busca; por eso se vuelve a ordenar con by_code antes de buscar.

La clave que se busca es un Product con solo el código relleno. bsearch devuelve un puntero al elemento encontrado o NULL, como pasa con el código 9999.

Código · main.c

#include <stdio.h>#include <stdlib.h>typedef struct { int code; const char *name; double price; } Product;// Comparators get two const void * and return <0, 0 or >0.int by_price(const void *a, const void *b) {    double x = ((const Product *)a)->price, y = ((const Product *)b)->price;    return (x > y) - (x < y);  // no subtraction: it could overflow or truncate}int by_code(const void *a, const void *b) {    int x = ((const Product *)a)->code, y = ((const Product *)b)->code;    return (x > y) - (x < y);}int main(void) {    Product shelf[] = {{3051, "Olive oil", 8.95}, {1007, "Bread", 1.20}, {2210, "Cheese", 6.40},                       {1530, "Milk", 0.99}, {4100, "Coffee", 4.75}};    size_t n = sizeof shelf / sizeof shelf[0];    qsort(shelf, n, sizeof shelf[0], by_price);    printf("By price:\n");    for (size_t i = 0; i < n; i++)        printf("  %4d %-10s %5.2f\n", shelf[i].code, shelf[i].name, shelf[i].price);    // bsearch needs the array sorted by the same key it searches for.    qsort(shelf, n, sizeof shelf[0], by_code);    printf("By code: first %d, last %d\n", shelf[0].code, shelf[n - 1].code);    int wanted[] = {2210, 9999};    for (int w = 0; w < 2; w++) {        Product key = {wanted[w], NULL, 0};        Product *hit = bsearch(&key, shelf, n, sizeof shelf[0], by_code);        printf("Code %d: %s\n", wanted[w], hit ? hit->name : "not found");    }    return 0;}

Salida · cc main.c -o main && ./main

By price:
  1530 Milk        0.99
  1007 Bread       1.20
  4100 Coffee      4.75
  2210 Cheese      6.40
  3051 Olive oil   8.95
By code: first 1007, last 4100
Code 2210: Cheese
Code 9999: not found

Para recordar

qsort(array, n, sizeof array[0], comparador) ordena cualquier tipo.
El comparador devuelve <0, 0 o >0; (x > y) - (x < y) es seguro.
bsearch exige el array ordenado por la misma clave.
bsearch devuelve un puntero al elemento o NULL.

Ejercicio

Escriba by_name con strcmp, ordene la estantería por nombre y busque "Milk" con bsearch.