Nona lezione

Il sistema più elementare per ricercare un dato specifico in una sequenza consiste nell'esaminare uno dopo l'altro tutti i dati presenti nella sequenza stessa.
Nel peggiore dei casi, (che può capitare molto spesso, per esempio se il dato richiesto non c'è...), dovremo esaminare tutti i dati della nostra collezione: un'operazione il cui costo dipende linearmente dal numero dei dati.

Certo, se i dati fossero ordinati in base alla grandezza sulla quale deve avvenire ricerca e se fosse possibile accedere direttamente ai dati secondo il loro numero d'ordine, potremmo tentare un approccio più astuto come quello di una ricerca binaria.

Per effettuare una ricerca binaria su un campione ordinato basta scegliere un punto in mezzo al campione e verificare se il valore che stiamo cercando è maggiore, minore (o uguale) al valore scelto. A questo punto basta continuare, ripetendo l'operazione sulla metà rimasta.

Vediamo il metodo in funzione in questo . Dal momento che procediamo continuando a dividere il campione a metà, all'aumentare del numero degli elementi del campione il numero di operazioni necessario per completare la ricerca cresce all'incirca secondo il logaritmo in base 2 del numero di elementi, quindi molto meno che linearmente.

In base a questi ragionamenti dovremmo ormai essere convinti che il problema della ricerca e quello dell'ordinamento sono strettamente imparentati. Quali sistemi abbiamo dunque a disposizione per mettere in ordine un campione di elementi disordinati?

In uno dei precedenti esempi abbiamo visto un possibile metodo (detto del "giocatore di carte", o anche insertion sort), che consiste nel prelevare uno ad uno gli elementi da inserire, e creare una nuova lista ordinata inserendo ogni elemento nella posizione giusta. Tale sistema non è particolarmente efficiente, come constateremo fra poco, ma presenta alcuni innegabili vantaggi: in primo luogo permette di effettuare l'ordinamento nella stessa area di memoria occupata dai dati, senza richiedere la copia in un'area supplementare (in-place sort). In secondo luogo è stabile, nel senso che non viene cambiata la posizione relativa degli elementi con chiave di ricerca uguale. Infine è adatto all'uso con le linked list (che non possono essere indirizzate in modo assoluto). In moltissime situazioni quindi questo sistema può risultare più che sufficiente.

Si può fare di meglio? Dato che questo non è un corso di informatica pura, tralasciamo l'analisi delle varie soluzioni inetrmedie, e saltiamo subito alla conclusione: un algoritmo di ordinamento senz'altro più efficiente per l'uso generale (di fatto è il migliore ora conisciuto) esiste, si chiama quicksort, e merita una descrizione accurata.

Supponiamo di avere una pila di libri da mettere in ordine alfabetico per autore. Possiamo iniziare scegliendo uno dei libri (ad esempio un autore che inizia con la "L" o con la "M") e dividendo i libri in due pile: una con tutti i libri che precedono in ordine alfabetico l'autore scelto, ed una con tutti i libri che seguono. A questo punto possiamo ripetere la procedura su ciascuna delle due pile ottenute. Continuando a dividere rimarremo con gruppetti di due o tre libri, ed infine con libri singoli, che a questo punto saranno in ordine alfabetico.
Ecco un altro esempio con i numeri, che ci aiuta a capire come questa strategia possa essere convertita in un algoritmo:

Osservando bene si nota che il caso nella figura è assolutamente ottimale! Ogni volta siamo riusciti a scegliere un elemento "separatore" che divide la collezione esattamente in due. Il problema principale del quicksort riguarda proprio la strategia utilizzata per scegliere l'elemento separatore. Può sembrare sorprendente che uno dei sistemi migliori per effettuare tale scelta sia quello di affidarsi al caso. Questa strategia è in pratica l'unica utilizzata, eventualmente con una sola miglioria: scegliere l'elemento intermedio fra tre scelti a caso.
Abbiamo utilizzato proprio quest'ultimo metodo (elemento intermedio scelto fra tre) nel seguente che illustra una implementazione del quicksort.

A questo punto sappiamo come ricercare rapidamente un array ordinato, e sappiamo anche come ordinarlo in modo efficiente. Come applicare il tutto ad una entità che può anche essere modificata efficientemente come una linked list? La soluzione (non particolarmente semplice) sta in un'applicazione delle strutture ad albero. Immaginiamo infatti di organizzare un albero in modo che sia possibile una ricerca binaria:

In questo modo possiamo aggiungere dinamicamente nodi all'albero, e garantirci l'ottimizzazione nella ricerca a patto che l'albero rimanga bilanciato, cioè che il numero dei rami di "destra" e di "sinistra" di ogni sottoalbero sia circa lo stesso.
Se immaginassimo di inserire nell'albero numeri già in ordine, infatti, l'albero degenererebbe in una lista...
Esistono sistemi per bilanciare automaticamente un albero di ricerca, il più noto dei quali è il metodo di Adel'son, Vel'sky e Landis (AVL), la cui discussione particolareggiata richiederebbe troppo tempo. Se a qualcuno interessa approfondire l'argomento, ecco gli esempi di codice tratti da K. Loudon, Mastering Algorithms with C (O' Reilly): bistree.h, bistree.h, bistree.h.

Come sempre, è possibile inventare criteri di ricerca e ordinamento diversi e ottimali per una certa applicazione. Pensiamo ad esempio a criteri di tipo lessicale (simili alla divisione in lettere degli elenchi telefonici), oppure a criteri di conteggio (contando la frequenza di apparizione di un certo elemento si può ricavare la posizione che avrà nella lista ordinata).

Spesso inoltre è velleitario sperare di poter organizzare i dati in una struttura ordinata in modo ottimale. Esiste tutto uno spettro di soluzioni intermedie (basate ad esempio strutture dati come le hash table), che offrono comunque il vantaggio di velocizzare la ricerca. I dati vengono "catalogati" in vari sottoinsiemi più piccoli, utilizzando soltanto qualche caratteristica intrinseca della chiave di ricerca. Come sempre, è l'applicazione a dettare la soluzione migliore, e trovare la soluzione migliore senza conoscere a priori l'applicazione è la grande sfida per i produttori di software per database.

Esercizio: Provare ad aggiungere un ciclo di ordinamento ad inserzione per la linked list dell'esercizio precedente.