Sesta lezione

Ricerca e ordinamento

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 la 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.

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?

Ordinamento per inserzione

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 contenitori come std::list (che non possono essere indirizzati 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 intermedie, e saltiamo subito alla conclusione: un algoritmo di ordinamento senz'altro più efficiente per l'uso generale (di fatto è il migliore ora conosciuto) esiste, si chiama quicksort, e merita una descrizione accurata.

Quicksort

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 (il libro scelto come "elemento separatore" può appartenere ad una qualsiasi delle due pile). 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 un'implementazione del quicksort.

Algoritmi di STL

Una delle principali ragioni dello sviluppo di template, contenitori e iteratori generici in C++ è la possibilità di offrire, attraverso di essi, una vasta collezione di algoritmi (procedure standard applicate a strutture dati standard, nel senso che offrono almeno iteratori come quelli descritti nella lezione scorsa). Quello che segue è solo il catalogo degli algoritmi disponibili nella libreria standard C++, ai quali si può accedere attraverso gli header file <algorithm> e <numeric>.

NOTA: Gli algoritmi elencati non possono aggiungere o rimuovere elementi dai contenitori. Le operazioni che danno l'impressione di poter rimuovere elementi spostano semplicemente gli elementi interessati alle estremità dei contenitori, dove possono essere più facilmente rimossi, oppure creano una copia del contenitore senza gli elementi interessati.

count(_if) Conta gli elementi che hanno un determinato valore, oppure (_if) per i quali una certa condizione è vera.
for_each Applica una funzione (o funtore, cioè oggetto che definisce operator() a ciascun elemento.
equal Determina se due gruppi di elementi hanno lo stesso contenuto (usando l'operatore == o un metodo definito dall'utente).
lexicographical_compare Determina se un gruppo di elementi, confrontati membro a membro atrtraverso l'operatore < o un metodo definito dall'utente come le lettere di una parola, è "minore" di un altro.
max_element Fornisce il valore massimo di un gruppo di elementi.
min_element Fornisce il valore minimo di un gruppo di elementi.
mismatch Fornisce la prima posizione nella quale due gruppi di elementi iniziano a differire.
adjacent_find Trova la prima posizione dove un elemento di un gruppo è uguale (== o metodo definito dall'utente) ad un elemento adiacente.
find(_if) Trova il primo elemento di un gruppo che ha un determinato valore (confrontato con == o metodo definito dall'utente), o per il quale (_if) una determinata condizione è vera.
search(_n) Trova la prima posizione dove un sottogruppo di elementi (o n elementi ripetuti nel caso _n) è presente all'interno di un gruppo di elementi. (Gli elementi vengono confrontati con == o un metodo definito dall'utente).
find_end Trova l'ultima posizione dove un sottogruppo di elementi è presente all'interno di un gruppo di elementi. (Gli elementi vengono confrontati con == o un metodo definito dall'utente).
find_first_of Trova la prima posizione dove si trova un elemento qualsiasi di un gruppo all'interno di un altro gruppo. (Gli elementi vengono confrontati con == o un metodo definito dall'utente).
binary_search Determina se un valore si trova o meno in un gruppo di elementi ordinato. Viene usato l'operatore <, o un operatore fornito dall'utente.
equal_range Trova i limiti inferiore e superiore dove si trova (o andrebbe inserito) un determinato valore in un gruppo di elementi ordinato. Viene usato l'operatore <, o un operatore fornito dall'utente.
lower_bound Trova il solo limite inferiore dove si trova (o andrebbe inserito) un determinato valore in un gruppo di elementi ordinato. Viene usato l'operatore <, o un operatore fornito dall'utente.
upper_bound Trova il solo limite superiore dove si trova (o andrebbe inserito) un determinato valore in un gruppo di elementi ordinato. Viene usato l'operatore <, o un operatore fornito dall'utente.
copy(_backward) Copia un gruppo di elementi compreso fra due iteratori nella posizione indicata da un altro iteratore, eventualmente iterando in ordine inverso.
fill(_n) Riempie un gruppo di elementi con un valore fissato.
generate(_n) Riempie un gruppo di elementi con valore ottenuto da una funzione.
iter_swap Scambia gli elementi puntati da due iteratori.
random_shuffle Riordina in modo casuale un gruppo di elementi.
remove(_if) Riordina un gruppo di elementi in modo da poter più facilmente rimuovere quelli che hanno un certo valore, oppure (_if) per i quali una certa condizione è vera.
remove_copy(_if) Copia un gruppo di elementi rimuovendo dalla copia quelli che hanno un certo valore, oppure (_if) per i quali una certa condizione è vera.
replace(_if) Cambia il valore degli elementi che hanno un certo valore originario, oppure (_if) per i quali una certa condizione è vera.
replace_copy(_if) Copia un gruppo di elementi cambiando valore a quelli che hanno un certo valore, oppure (_if) per i quali una certa condizione è vera.
reverse(_copy) Inverte l'ordine di un gruppo di elementi, eventualmente generando una copia.
rotate(_copy) Fa ruotare (sposta elementi dalla testa alla coda, o viceversa) un gruppo di elementi, eventualmente generando una copia.
swap_ranges Scambia i valori di due gruppi di elementi.
transform Applica una funzione di trasformazione a un gruppo di elementi.
unique(_copy) Riordina un gruppo di elementi in modo da poter più facilmente eliminare tutti quelli ripetuti ed adiacenti, eventualmente generando una copia.
sort Riordina gli elementi in ordine ascendente. Viene usato (come in tutte le funzioni di sort) l'operatore <, o un operatore fornito dall'utente.
stable_sort Riordina gli elementi in ordine ascendente, in modo stabile, cioè mantenendo l'ordine relativo che gli elementi con lo stesso valore avevano originariamente. Viene usato (come in tutte le funzioni di sort) l'operatore <, o un operatore fornito dall'utente.
partial_sort(_copy) Riordina (o copia nel caso di _copy) un gruppo di elementi in modo che solo la prima parte sia ordinata.
nth_element Trova l'elemento che corrisponderebbe alla posizione n se un gruppo di elementi fosse ordinato, e riordina il gruppo in modo da separare tutti gli elementi inferiori all'n-esimo e quelli uguali e superiori (sostanzialmente la procedura usata nel quicksort).
partition Riordina un gruppo di elementi in modo che tutti quelli per cui una determinata condizione è vera vengano prima di quelli per cui la stessa condizione è falsa.
stable_partition Riordina un gruppo di elementi in modo che tutti quelli per cui una determinata condizione è vera vengano prima di quelli per cui la stessa condizione è falsa, in modo stabile, cioè mantenendo l'ordine relativo che gli elementi appartenenti allo stesso gruppo avevano originariamente.
inplace_merge Unisce due gruppi di elementi consecutivi e già ordinati in un solo gruppo ordinato, che sostituisce i due precedenti ("in place").
merge Unisce due gruppi di elementi già ordinati e crea un nuovo gruppo ordinato.
includes Determina se un gruppo di elementi ordinato è contenuto in un altro.
set_intersection Copia l'intersezione fra due gruppi di elementi ordinati in un nuovo gruppo.
set_simmetric_difference Copia la differenza simmetrica (complementare dell'intersezione) fra due gruppi di elementi ordinati in un nuovo gruppo.
set_difference Copia la differenza (elementi di un gruppo ordinato che non stanno anche in un secondo gruppo ordinato) in un nuovo gruppo.
set_union Copia l'unione di due gruppi di elementi ordinati in un nuovo gruppo.
make_heap Riordina gli elementi di un gruppo in modo che il primo elemento sia il più grande, e sia possibile aggiungere e rimuovere elementi in modo efficiente (mettendoci un tempo dell'ordine di log2n), così che il gruppo risultante abbia la stesse proprietà (di avere l'elemento più grande in testa). Viene usato, come per gli altri algoritmi di heap l'operatore <, o un metodo fornito dall'utente.
pop_heap Estrae l'elemento di testa di un gruppo, e riordina il gruppo in modo che conservi la proprietà di avere l'elemento più grande in testa.
push_heap Inserisce un nuovo elemento in testa ad un gruppo, e riordina il gruppo in modo che conservi la proprietà di avere l'elemento più grande in testa.
sort_heap Riordina completamente un gruppo di elementi che ha già la proprietà di avere l'elemento più grande in testa.
next_permutation Genera la successiva permutazione di un gruppo di elementi, scambiandone due. Quando tutte le possibili permutazioni sono state eseguite, questo algoritmo restituisce il valore booleano false.
prev_permutation Genera la precedente permutazione di un gruppo di elementi, scambiandone due. Quando viene nuovamente incontrata la prima permutazione, questo algoritmo restituisce il valore booleano false.

Vediamo dunque in questo quanto si semplifica l'esempio precedente se si delegano ad opportuni algoritmi di STL sia l'ordinamento che la ricerca binaria degli elementi.

Esercizio: Inserire nell'esercizio della lezione scorsa un ordinamento delle sfere (i cui dati vengono definiti staticamente) per raggio crescente.