Tecniche di Programmazione: Divide et Impera

In questo post l'intenzione è quella di scrivere uno schema della tecnica divide et impera, basandomi sugli appunti presi a lezione e sul libro di testo (Algoritmi e Strutture Dati di Demetrescu, Italiano, Finocchi edito dalla McGraw Hill). Per qualsiasi suggerimento o altro lasciate un commento o contattateci!

Principio: Principalmente si compone di due passi:
Passo Divide: Dividere i dati in ingresso in due o più sottoinsiemi tramite la ricorsione.
Passo Impera: Risolvere il problema sui sottoinsiemi e ricombinare le varie soluzioni per ottenere la soluzione globale. Considera il problema con un approccio top-down.

Punti di forza: l'efficacia aumenta se il problema è facilmente scomponibile.
Punti di debolezza: Richiede uno sforzo per individuare tecniche per la decomposizione e la ricombinazione: non è immediato e banale trovare il passo Divide e il passo Impera.

Esempio: QuickSort
Il quick sort è un algoritmo di ordinamento. Il suo funzionamento applicato ad un array è il seguente:
Divide: Sceglie a caso un indice x (la scelta casuale dell'indice diminuisce la complessità dell'algoritmo) e partiziona la sequenza in modo tale che una sequenza contenga elementi <= ad Array[x] e l'altra contenga elementi >Array[x]. (questo processo è ricorsivo)
Impera: unisce la sottosequenze ordinate.

Procedura partition (array A, indici i, f ) → indice
x ← A[i] 

inf ← i
sup ← f +1
stop = false
while ( !stop ) do
do inf ← inf + 1
while ( inf <= f and A[inf] <= x )
do sup ← sup – 1
while ( A[sup] > x )
if ( inf < sup )
scambia ( inf , sup ) // scambia A[inf] con A[sup]
else
stop = true
scambia (i , sup ) // scambia A[i] con A[sup]
return sup

Esempio di procedura Partition [Wikipedia]

algoritmo quicksort (array A, indici i, f )
if ( i >= f )
return
m ← partition (A,i,f)
quicksort (A,i,m-1)
quicksort (A,m+1,f)

Praticamente l'algoritmo si può sintetizzare così:

Dato un array in input e due indici i ed f, rispettivamente la posizione iniziale e la posizione finale dell'array (nella prima chiamata), esegui quicksort: se abbiamo più di un elemento (la condizione dell'if) salvami in m il risultato della partizione del mio array attuale (l'indice posizionato correttamente dopo l'esecuzione di partition) e chiama la funzione quicksort (ricorsione) sulle due parti prima di m e dopo di m (le parti ancora “in dubbio”, quindi da ordinare).

La funzione partition funziona così:

Metti in inf l'indice i e in sup l'indice f; inizializza a falso la variabile booleana stop che ci dirà quando abbiamo finito la chiamata di funzione; ora:
→ scorri verso destra l'array tramite l'indice inf e fermati solo quando trovi un elemento più grande di x ( che ricordiamo è ora A[i] ) oppure se con l'indice inferiore hai sorpassato ( o sei sulla stessa posizione) l'indice superiore ( ho visitato tutti gli elementi ).
→ scorri verso sinistra l'array tramite l'indice sup e fermati solo quando trovi un elemento più piccolo o uguale a x. (in questo caso è ridondante inserire un controllo che si ferma se arriva all'indice inf o lo supera, dato che, in caso li scorre tutti da destra, si fermerà sicuramente alla posizione i, dato che A[i] è sicuramente = ad x e ciò fa interrompere il ciclo).
In questo modo ci fermiamo quando A[inf] sarà maggiore di x e A[sup] sarà minore o uguale ad x. A questo punto li scambiamo, così avremo nella parte destra tutti i numeri maggiori di x e nella parte sinistra tutti i numeri minori.

Quando l'indice inf avrà superato (o raggiunto) l'indice sup, significa che ho fatto tutti i confronti e dunque poniamo stop = true, che farà fermare il ciclo. L'ultimo passo è quello di scambiare l'elemento perno, A[i], con A[sup], il che porterà l'elemento A[i] nella sua posizione finale e avrà alla sua sinistra i numeri minori o uguali e alla sua destra i numeri maggiori.

Se come perno usiamo ogni volta il primo elemento nell'array (quindi come i usiamo 0) potremmo avere il caso peggiore che A[0] sia l'elemento più piccolo o più grande dell'array e dunque la complessità dell'algoritmo sarà O(n^2). Per rendere più efficiente la complessità, scegliamo come indice i, un numero casuale, portandola a O (n log n). 

Quicksort. Le linee orizzontali sono gli indici scelti (pivot) [Wikipedia]