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 - iniziodiminuisce in entrambi i rami. Calcoliamomedio = inizio + (fine - inizio) / 2per 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 array | Miglior caso, se utile | Caso peggiore | Spazio ausiliario | Stabile |
|---|---|---|---|---|
| Bubble con arresto anticipato | Sì | |||
| Insertion con confronti stretti | Sì | |||
| Selection con scambio | No | |||
| Merge sort con buffer | Sì, scegliendo prima la metà sinistra a parità | |||
| Quicksort con partizione in loco e due chiamate ricorsive | con partizioni bilanciate | nel caso peggiore per lo stack | No, con partizione per scambi | |
| Heapsort con ripristino iterativo | No |
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: 0Errori frequenti
Errori da evitare
Errore · Calcolare il punto medio con
(inizio + fine) / 2o leggerev[n]a fine ricerca.Correzione · Usare
inizio + (fine - inizio) / 2e controllareinizio < nprima 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
qsortdeve 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?
Soluzione
Un controllo nel primo caso e otto nel secondo.
Esercizio 2. Prima occorrenza (Base)
Esegui la ricerca binaria della prima occorrenza di 4 in [1, 4, 4, 9].
Soluzione
[0,4)prova l’indice2e diventa[0,2). Si prova l’indice1e si ottiene[0,1). L’indice0contiene1, quindi si chiude su[1,1). L’elemento all’indice1è4.
Esercizio 3. Quando uno scambio perde stabilità (Intermedio)
Mostra il primo passo del selection sort su [2a, 2b, 1].
Soluzione
Il minimo
1viene scambiato con2a. Si ottiene[1, 2b, 2a], con i record di chiave2in ordine inverso.
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?
Soluzione
Le lunghezze dei segmenti fusi a ogni livello sommano a . Il lavoro è per livello. Ci sono livelli di fusione, quindi il costo è .
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.
Soluzione
Il pivot è ogni volta il minimo. Una parte è vuota e l’altra ha lunghezza . Sommando il lavoro proporzionale a otteniamo .
Esercizio 6. Comparatore con estremi (Avanzato)
Quale segno deve restituire il comparatore per INT_MIN e INT_MAX? Perché la sottrazione è pericolosa?
Soluzione
Il risultato deve essere negativo. La differenza matematica è minore di
INT_MINe causerebbe overflow con segno. Con i confronti si ottiene0 - 1, rappresentabile.
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.