Algoritmi di ricerca e ordinamento

Quando conviene ordinare prima di cercare

Se cerchiamo una sola volta in un array disordinato, possiamo visitarlo da sinistra a destra. Se i dati sono già ordinati, a ogni confronto possiamo escludere una parte dell’array. Quando le ricerche sono molte, ha senso confrontare il costo della preparazione con quello delle interrogazioni. Per ricerche su elementi, una scansione per ricerca costa nel caso peggiore . Un ordinamento per fusione seguito da ricerche binarie costa per . Le scritture successive possono cambiare la scelta.


Ricerca lineare e binaria

La ricerca lineare esamina gli elementi in ordine e può restituire la prima occorrenza o indicare che la chiave è assente. Usa spazio ausiliario costante e al più controlli. Funziona anche quando l’array è vuoto o disordinato.

La ricerca binaria richiede che i dati siano ordinati secondo lo stesso criterio usato nei confronti. Per trovare la prima posizione il cui valore è maggiore o uguale alla chiave, manteniamo l’intervallo semiaperto [inizio, fine) di elementi ancora da verificare. Prima di inizio tutti i valori sono minori della chiave. Da fine in avanti sono maggiori o uguali. Se v[medio] < chiave, spostiamo inizio a medio + 1. Altrimenti spostiamo fine a medio. All’uscita, l’indice può valere n. Per confermare la presenza, controlliamo il limite e l’uguaglianza.

Riduzione dell'intervallo

La quantità fine - inizio diminuisce in entrambi i rami. Calcoliamo medio = inizio + (fine - inizio) / 2 per evitare una somma intermedia fuori intervallo.

In un array l’indice mediano dimezza l’intervallo. Un albero binario di ricerca scarta invece un sottoalbero e il costo dipende dall’altezza. La nota sui costi distingue modello, spazio ausiliario e distribuzione degli ingressi.


Ordinamenti elementari e avanzati

Un ordinamento è stabile se mantiene l’ordine relativo degli elementi con chiave uguale. Serve per record che conservano informazioni oltre alla chiave.

  • Bubble sort. Scambiamo coppie adiacenti fuori ordine. Una passata porta il massimo del prefisso non ancora sistemato al suo estremo destro. Se una passata non scambia nulla, l’array è ordinato. Scambiare solo quando la prima chiave è strettamente maggiore conserva la stabilità.
  • Insertion sort. Il prefisso è già ordinato. Inseriamo il prossimo elemento facendo scorrere a destra i valori strettamente maggiori. L’invariante si estende al prefisso successivo. Funziona bene su dati già quasi ordinati.
  • Selection sort. Cerchiamo il minimo della parte ancora da ordinare e lo scambiamo con il suo primo elemento. Il prefisso contiene in ordine i valori più piccoli. Lo scambio può invertire record equivalenti.
  • Merge sort. Dividiamo l’array in due metà, le ordiniamo ricorsivamente e le fondiamo in tempo lineare. In caso di parità, prelevare prima dalla metà sinistra mantiene l’ordine relativo. Su array una fusione con buffer riutilizzato richiede spazio ausiliario lineare.
  • Quicksort. Partizioniamo attorno a un pivot e riapplichiamo il metodo alle parti più piccole. Con chiavi distinte e pivot casuale uniforme il tempo atteso è . Suddivisioni ripetute in parti di dimensione e portano a .
  • Heapsort. Costruiamo un max-heap in tempo lineare con ripristini dal basso. Scambiamo la radice con l’ultima cella del prefisso attivo, riduciamo il prefisso e ripristiniamo l’heap. Il suffisso contiene gli elementi già in ordine. Un ripristino iterativo richiede spazio ausiliario costante.
Versione su arrayMiglior caso, se utileCaso peggioreSpazio ausiliarioStabile
Bubble con arresto anticipatoSì
Insertion con confronti strettiSì
Selection con scambioNo
Merge sort con bufferSì, scegliendo prima la metà sinistra a parità
Quicksort con partizione in loco e due chiamate ricorsive con partizioni bilanciate nel caso peggiore per lo stackNo, con partizione per scambi
Heapsort con ripristino iterativoNo

Esempi guidati

Esempio 1. Fondere due metà ordinate

Problema. Fondere [2a, 6] e [2b, 5] in ordine crescente. Le lettere identificano record con la stessa chiave.

Svolgimento. Confrontiamo le prime posizioni disponibili. A parità prendiamo 2a dalla metà sinistra, poi 2b dalla destra. Confrontiamo 6 e 5, scegliamo 5 e infine copiamo 6. Il risultato [2a, 2b, 5, 6] è stabile. Ogni passo trasferisce un elemento e il numero di passi è la lunghezza totale.

Esempio 2. Ordinare interi con qsort e cercare la prima occorrenza

Problema. Ordinare un array con duplicati e trovare il primo 2. Verificare anche una chiave assente e il caso vuoto.

Svolgimento. qsort riceve indirizzo, numero di elementi, dimensione di un elemento e comparatore. Il comparatore restituisce un valore negativo, zero o positivo secondo l’ordine. I due confronti evitano l’overflow che una sottrazione come a - b potrebbe causare. Dopo l’ordinamento usiamo l’invariante della ricerca binaria. Il C11 non specifica l’algoritmo né garantisce la stabilità di qsort.

Programma completo C11.

#include <limits.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
 
static int confronta_int(const void *primo, const void *secondo)
{
    int a = *(const int *)primo;
    int b = *(const int *)secondo;
    return (a > b) - (a < b);
}
 
static size_t cerca_primo(const int v[], size_t n, int chiave)
{
    size_t inizio = 0;
    size_t fine = n;
    while (inizio < fine) {
        size_t medio = inizio + (fine - inizio) / 2;
        if (v[medio] < chiave) {
            inizio = medio + 1;
        } else {
            fine = medio;
        }
    }
    return inizio < n && v[inizio] == chiave ? inizio : n;
}
 
int main(void)
{
    int v[] = {2, INT_MAX, -4, 2, INT_MIN};
    size_t n = sizeof v / sizeof v[0];
    qsort(v, n, sizeof v[0], confronta_int);
 
    printf("Primo 2: %zu\n", cerca_primo(v, n, 2));
    printf("Assente: %zu\n", cerca_primo(v, n, 3));
    printf("Vuoto: %zu\n", cerca_primo(NULL, 0, 2));
    return 0;
}

Output atteso

Primo 2: 2
Assente: 5
Vuoto: 0

Errori frequenti

Errori da evitare

Errore · Calcolare il punto medio con (inizio + fine) / 2 o leggere v[n] a fine ricerca.

Correzione · Usare inizio + (fine - inizio) / 2 e controllare inizio < n prima di accedere.

Errore · Supporre che qualunque ordinamento conservi l’ordine delle chiavi uguali.

Correzione · Verificare cosa accade quando il confronto vale zero. Per qsort, aggiungere un secondo criterio, per esempio l’indice originale, se quell’ordine è un requisito.

Errore · Dare al comparatore un puntatore al tipo sbagliato o restituire a - b.

Correzione · Usare il tipo degli elementi effettivi e restituire il segno tramite confronti. La dimensione passata a qsort deve coincidere con quella di un elemento.


Esercizi di prova

Esercizio 1. Costo della scansione (Base)

In un vettore di 8 elementi, quanti controlli di uguaglianza fa una ricerca lineare se la chiave è al primo posto? E se è assente?

Esercizio 2. Prima occorrenza (Base)

Esegui la ricerca binaria della prima occorrenza di 4 in [1, 4, 4, 9].

Esercizio 3. Quando uno scambio perde stabilità (Intermedio)

Mostra il primo passo del selection sort su [2a, 2b, 1].

Esercizio 4. Perché il merge sort costa n log n (Intermedio)

Supponi che sia una potenza di due e che ogni fusione richieda tempo lineare nella lunghezza totale. Quanto lavoro si fa a ciascun livello?

Esercizio 5. Pivot estremo (Avanzato)

Un quicksort su chiavi distinte sceglie sempre la prima chiave come pivot e riceve un array crescente. Ricava il costo se la partizione è lineare, esclude il pivot dal problema successivo e lascia in ordine gli elementi rimanenti.

Esercizio 6. Comparatore con estremi (Avanzato)

Quale segno deve restituire il comparatore per INT_MIN e INT_MAX? Perché la sottrazione è pericolosa?


Provenienza del materiale

  • Marco Anisetti, Algoritmi e strutture dati dinamiche, C1PROG1_Appunti_di_fine_unità_6.pdf, cap. 3, pp. 51–107 della numerazione stampata.
  • WG14, bozza C11 N1570, § 7.22.5.2.