C/C++

Tema 7 · Algorismes de cerca i ordenació

Introducció

La cerca permet trobar elements dins d'una col·lecció (vectors, llistes). L'ordenació reorganitza les dades segons un criteri (p. ex., de menor a major). En C disposem de funcions de la biblioteca estàndard com qsort() i bsearch() que implementen algorismes eficients (QuickSort i cerca binària). Aquestes eines són fonamentals per processar grans volums de dades biomèdiques, com llistes de proteïnes o gens.

Objectius

  • Implementar cerques lineals i entendre el seu cost
  • Utilitzar qsort() per ordenar vectors de qualsevol tipus
  • Utilitzar bsearch() per cercar en vectors ordenats
  • Crear funcions de comparació personalitzades per a structs

Algorismes de cerca

Cerca lineal: recórrer tot el vector fins trobar l'element. Senzill però costós per a conjunts grans.

#include <stdio.h>

int cerca_linial(int arr[], int n, int objectiu) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == objectiu) return i;
    }
    return -1;  // no trobat
}

int main() {
    int dades[] = {12, 45, 23, 51, 8, 17};
    int n = 6, buscat = 51;
    
    int pos = cerca_linial(dades, n, buscat);
    if (pos != -1)
        printf("Trobat a la posició %d.\n", pos);
    else
        printf("No trobat.\n");
    return 0;
}
Retorna l'índex o -1 si no el troba

Cerca binària (bsearch()): molt més ràpida, però el vector ha d'estar ordenat.

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

int comparar(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int dades[] = {8, 12, 17, 23, 45, 51};
    int n = 6, clau = 23;
    
    int *trobat = (int*) bsearch(&clau, dades, n, sizeof(int), comparar);
    if (trobat != NULL)
        printf("Trobat: %d\n", *trobat);
    else
        printf("No trobat.\n");
    return 0;
}
La funció de comparació ha de retornar negatiu, zero o positiu

Ordenació amb qsort()

qsort() implementa l'algorisme QuickSort i pot ordenar qualsevol tipus de dades, sempre que li passem una funció de comparació. 

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

// Ordenar enters
int comparar_enters(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);  // ascendent
}

// Ordenar cadenes (alfabètic)
int comparar_cadenes(const void *a, const void *b) {
    return strcmp(*(char**)a, *(char**)b);
}

int main() {
    int valors[] = {51, 8, 45, 17, 23, 12};
    int n = 6;
    qsort(valors, n, sizeof(int), comparar_enters);

    printf("Valors ordenats: ");
    for (int i = 0; i < n; i++) printf("%d ", valors[i]);
    printf("\n");

    // Amb cadenes
    char *animals[] = {"gat", "gos", "àguila", "balena", "cavall"};
    int m = 5;
    qsort(animals, m, sizeof(char*), comparar_cadenes);

    printf("Animals ordenats: ");
    for (int i = 0; i < m; i++) printf("%s ", animals[i]);
    printf("\n");

    return 0;
}
qsort() requereix: array, nombre d'elements, mida de cada element, funció comparació

Ordenar structs amb qsort()

Per ordenar un array de structs, la funció de comparació rep punters als elements (punters a struct). 

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

struct Proteina {
    char nom[50];
    int longitud;
};

// Comparar per longitud (ascendent)
int comparar_per_longitud(const void *a, const void *b) {
    struct Proteina *p1 = (struct Proteina *)a;
    struct Proteina *p2 = (struct Proteina *)b;
    return p1->longitud - p2->longitud;
}

// Comparar per nom (alfabètic)
int comparar_per_nom(const void *a, const void *b) {
    struct Proteina *p1 = (struct Proteina *)a;
    struct Proteina *p2 = (struct Proteina *)b;
    return strcmp(p1->nom, p2->nom);
}

int main() {
    struct Proteina llista[] = {
        {"Hemoglobina", 141},
        {"Insulina", 51},
        {"Albúmina", 585},
        {"Col·lagen", 1052}
    };
    int n = 4;

    qsort(llista, n, sizeof(struct Proteina), comparar_per_longitud);

    printf("Ordenades per longitud:\n");
    for (int i = 0; i < n; i++) {
        printf("  %s (%d aa)\n", llista[i].nom, llista[i].longitud);
    }

    return 0;
}
Funció de comparació rep dos const void* i els converteix al tipus adequat

Exercicis

  1. Implementa una cerca lineal per trobar un nom de proteïna en un array de structs. Si la troba, mostra'n la longitud.
  2. Ordena un vector de floats (pH de mostres) amb qsort() de manera ascendent i mostra el resultat.
  3. Crea una funció de comparació que ordeni proteïnes per longitud de manera descendent i busca la més llarga amb bsearch().

Mini Projecte – Ordenació de proteïnes per longitud

Escriu un programa que:

  • Llegeixi dades de proteïnes des d'un fitxer (nom i seqüència) i les emmagatzemi en un array dinàmic de structs (usa malloc()).
  • Calculi la longitud de cada proteïna a partir de la seqüència.
  • Permeti a l'usuari triar el criteri d'ordenació: per nom (alfabètic) o per longitud (ascendent o descendent).
  • Utilitzi qsort() amb funcions de comparació personalitzades per a cada criteri.
  • Mostri la llista ordenada per pantalla i la guardi en un fitxer proteines_ordenades.txt.

Ampliació: afegeix cerca binària per trobar una proteïna concreta per nom un cop ordenada alfabèticament.

Tema 6 Índex Tema 8