Esercizi svolti di informatica n.1

Dato un array di n numeri reali, progettare un algoritmo efficiente rispetto al tempo ed allo spazio, che posizioni tutti gli elementi negativi prima di tutti gli elementi positivi.

Calcolare la complessità temporale e spaziale dell’algoritmo presentato.

SOLUZIONE.

Innanzi tutto, si assuma, senza perdere di generalità, che lo 0 non sia presente tra i reali in input (se c’è, invece di trattare elementi negativi e positivi, si possono trattare, ad esempio, elementi negativi e non negativi).

Si osservi ora che separare gli elementi positivi dai negativi equivale ad ordinare n numeri interi nel range [0,1]; si può quindi applicare una modifica dell’algoritmo di counting sort, come segue.

Sia A l’array di input e B l’array di output, entrambi di lunghezza n.

Funzione SeparaPositiviNegativi(A, B)

int pos = 1; neg = n;

FOR i = 1 TO n DO

IF A[i]>0 THEN

B[pos] = A[i];

pos++;

ELSE

B[neg] = A[i];

neg--;

Si osservi che non abbiamo bisogno del terzo array C, avendo solo due tipi di elementi e non essendoci richiesto di mantenere l’ordinamento dato in input; infatti, l’algoritmo proposto posiziona gli elementi positivi nell’ordine dato e gli elementi negativi nell’ordine inverso.

La complessità temporale di questo algoritmo è, ovviamente, lineare in n, visto che il suo pseudocodice è costituito da un ciclo FOR che esegue operazioni costanti ad ogni iterazione. La complessità spaziale è anch’essa lineare in n, visto che l’lagoritmo utilizza, oltre al vettore di input A, un vettore ausiliario B di lunghezza n e tre contatori.

Un altro modo di procedere viene dall’osservazione che la suddivisione tra positivi e negativi può essere considerata come il risultato della procedura PARTITION, dove la soglia sia settata a 0.

In tal caso si può procedere come segue:

Funzione SeparaPositiviNegativi2(A)

i = 1; j = n;

WHILE (i < j)

WHILE (A[i]>0 AND i < j) DO

i++;

WHILE (A[j]<0 AND i < j) DO

j--;

SWAP(A[i], A[j]);

i++; j--;

Anche questa funzione ha complessità temporale lineare in n, infatti i due indici i e j permettono di scorrere una sola volta il vettore.

La complessità spaziale è, anch’essa lineare in n, poiché l’input è di dimensione n. Tuttavia, si osservi che – se non consideriamo il vettore di input – la prima soluzione richiede uno spazio aggiuntivo O(n), mentre la seconda O(1). Se ne conclude che, ai fini dell’efficienza richiesta, la seconda versione è lievemente da preferirsi rispetto alla prima.