Lezione XVI                                                frames      noframes

 

Ordinamento e ricerca

 

Ordinare e ricercare dei dati secondo determinati criteri e’ una delle operazioni piu’ importanti nell’ambito dell’elaborazione elettronica.

Tratteremo in questa lezione dell’ordinamento degli array secondo gli algoritmi di selezione e bubble sort e della ricerca degli elementi nell’array secondo il metodo sequenziale ed attraverso la ricerca binaria.

 

Ordinamento con Selection sort

 

Algoritmo ordinamento per selezione

 

Dato un array A, composto da n elementi, lo si vuole ordinare in senso crescente ( dal piu’ piccolo al piu’ grande).

L’ algoritmo confronta il primo elemento del nostro array, assunto come minimo parziale, con il generico elemento,  i-esimo, per i che varia da 2 fino ad n.

Se l’elemento i-esimo e’ piu’ piccolo del primo elemento allora essi vengono scambiati di posto fra loro ed il minimo viene aggiornato altrimenti se l’i_esimo elemento e’ maggiore del primo elemento tutto rimane immutato. Notate che in ogni passo si trova in prima posizione l’elemento piu’ piccolo fra quelli confrontati, fino al termine di tale iterazione dove l’elemento piu’ piccolo di tutto l’array viene a trovarsi in prima posizione.

A questo punto si esegue la operazione di ordinamento fra gli elementi compresi fra il secondo e l’ennesimo; cioe’ si esegue un confronto fra il secondo (nuovo minimo) ed il terzo, fra il secondo ed il quarto fino a confrontare il secondo con l’ennesimo ; ogni volta che dal confronto si trova un elemento piu’ piccolo si esegue uno scambio di posizione fra gli elementi oggetti del confronto ed un aggiornamento del minimo.

Al termine di questa iterazione avremo che in posizione 2 compare l’elemento piu’ piccolo fra gli n-1 elementi che erano rimasti da confrontare.

 

Il tutto viene ripetuto per il terzo il quarto … fino allo (n-1)-esimo elemento

Al termine si avra’ che lo i-esimo elemento dell’array ha un valore minore od uguale dell’elemento (i+1)-esimo per i = 1,2, 3, …. ,n-1 ,ossia alla fine del nostro algoritmo l’array risulta completamente ordinato.

 

La selezione, quindi seleziona l’elemento con valore minore e lo scambia con il primo elemento. Tra gli n-1 elementi rimasti viene poi ricercato quello con valore minore e scambiato con il secondo e cosi’ di seguito fino all’ultimo elemento.

 

Consideriamo un  esempio  grafico

 

Supponiamo di avere il seguente array di interi  int A[4]={55,12,44,9} e di volerlo ordinare in senso crescente, al crescere dell’ indice dell’array.

 

 

 

A 

55	12	44	9
0	1	2	3

 

Nella iterazione i-esima si assume come valore minimo l’elemento i-esimo dell’array per per i = [0 fino ad n-2] . Ad ogni passo il confronto avviene col minimo elemento, suscettibile di eventuali aggiornamenti nei passi precedenti.

 

1) Iterazione

Passo 1) minimo=55; confrontiamo 12 con 55 : if(12<55) si ed allora li scambiamo di posto ed aggiorniamo il valore minimo, avremo quindi

 

 

A’ 

12

55

44

9

 

 

 

Passo 2) nuovo minimo=12; confrontiamo 44 con 12 : if(44<12) no ed allora non avviene nessuno scambio

 

 

      A’’

12

55

44

9

 

 

 

Passo 3) minimo=12; confrontiamo 9 con 12 : if(9<12) si ed allora scambiamo i due elementi fra loro:

 

      A’’’

9

55

44

12

 

Nella prima iterazione dopo n-1 passi abbiamo ordinato il primo elemento dell’array essendo nel nostro caso n=4 ci sono occorsi 3 passi.

 

2) Iterazione

Passo 1)minimo=55; confrontiamo il 44 con il 55 : if(44<55) si ed allora scambiamo i due elementi fra  loro:

 

      A’’’’   

9

44

55

12

 

 

Passo2) minimo=44; confrontiamo il 12 con il 44 : if(12<44) si ed allora scambiamo i due elementi fra  loro:

       A’’’’’

9

12

55

44

 

Nella seconda iterazione dopo n-2 passi abbiamo ordinato il secondo elemento dell’array ed essendo n=4 avremo che sono serviti soltanto 2 passi per tale ordinamento

 

3) Iterazione

 

Passo 1) minimo=55; confrontiamo il 44 con il 55 : if(44<55) si ed allora scambiamoli fra loro

 

      A’’’’’’

9

12

44

55

 

A questo punto l’array e’ ordinato, avendovi impiegato 6 passaggi

Sono serviti 3 passi nella prima iterazione 2 passi nella seconda iterazione ed 1 passo nella terza iterazione, per cui in totale 3+2+1= 6 passi.

Ad ogni passo viene eseguito sempre un confronto mentre non e’ detto venga eseguito lo scambio.

 

In generale occorrono (n-1) iterazioni;

nella prima iterazione occorrono n-1 confronti; nella seconda iterazione occorrono n-2 confronti ; nella terza iterazione n-3 confronti eccetera fino alla (n-1)-esima iterazione dove serve un solo confronto.

 

Per cui il numero di confronti totali che e’ pari al numero totale di passi dell’algoritmo e’ dato dalla seguente formula:

(n-1) + (n-2) +( n-3) +…+2+1 che e’ uguale a  n * (n-1)/2

ossia coincide con la formula di Gauss che calcola la somma dei primi n-1 numeri interi positivi.

Nel nostro esempio n=4 , ergo possiamo sapere a priori che il numero di confronti o passi totali che l’algoritmo richiede e’ pari a:

n*(n-1)/2 = 4*(4-1)/2 = 6.

Si suole dire in letteratura che l’algoritmo ha un costo dato da n*(n-1)/2; ossia la complessita’ dell’algoritmo dipende dal numero n di elementi da ordinare ed ha sempre lo stesso costo per ogni possibile configurazione dei dati di ingresso. Notiamo pure che anche se l’array fosse ordinato vengono effettuati lo stesso n*(n-1)/2 confronti.

Essendo n*(n-1)/2= (n^2 -n)/2 si ha che il costo dell’algoritmo ordinamento per selezione e’ quadratico, ossia cresce all’incirca con il quadrato di n.

 

Una possibile pseudo_codifica dell’algoritmo selection sort e’ la seguente:

 

 selection_sort (A):

1. per ogni i=1,2,….,n  ripeti:
2. trova l’elemento minimo nel vettore A e ponilo in posizione i-esima
3. end.

 

Una possibile rappresentazione in linguaggio C di una funzione che usa tale algoritmo e’ la seguente,

in cui A e’ l’array di interi passato come parametro ed n e’ il numero di interi letti, anche esso passato come parametro :

 

void selection_sort(int A[ ], int n)

{

 int i, j, i_minimo;

 for ( i=0;i<n-1; i++) /*iterazione*/

  {

   /*ricerca della componente minima fra A[i] e A[n]*/

   i_minimo=i;

   for(j=i+1;j<n;j++)   /*passi*/

    if(A[j]<A[i_minimo]) /*confronto*/

    i_minimo= j;

    scambia(A[j],A[i_minimo] );

  }

}

 

nota : int A[ ];  passato come parametro alla funzione selection-sort  lo avremmo potuto sostituire con int *A  “puntatore all’array";

e’ evidente che dobbiamo fornire anche come parametro la dimensione dell’array, poiche’ nel passaggio di un array ad una funzione questa riceve l’indirizzo di memoria relativo al primo elemento dell’array.

L’indirizzo non fornisce nessuna informazione riguardo al numero di elementi presenti nel vettore e quindi e’ compito del programmatore fornire tale numero alla funzione.

nota :  scambia(A[j],A[i_minimo] ) naturalmente e' una funzione  C da progettare, da parte del programmatore, facendo uso di una varabile di appoggio.

 

Esercizio

 

 

Selection-sort interattivo

 

 

Ordinamento a bolle

 

Supponiamo di voler risolvere  un semplice problema di ordinamento: ordinare in senso crescente, i valori contenuti in un vettore di nome VET formato da n = 10 elementi di tipo intero.

Usiamo l’algoritmo  bubble sort  (ordinamento a bolle) dove gli elementi piu’ piccoli salgono gradualmente in cima al vettore (verso la posizione zero).

Noi considereremo il caso in cui gli elementi piu’ grandi scendono come bolle verso la posizione finale del vettore (posizione n-1 esima)

Esso si basa sul principio che presi due elementi adiacenti in un array ordinato, VET[i] e VET[i+1], si ha che 

VET[i] <= VET[i+1] .

Con l’algoritmo bubble sort vengono confrontate ripetutamente coppie di elementi adiacenti, le quali vengono scambiate se non rispettano l’ordinamento. Precisamente l’elemento VET[0] viene confrontato con l’elemento VET[1] e se risulta che VET[0]>VET[1]  i due elementi vengono scambiati; poi si confronta VET[1] con VET[2] ed in generale l’ elemento VET[i] con l’elemento VET[i+1] finche’  

i vale:  n - 1 - numero_di_iterazione_attuale .

Durante questa prima iterazione gli elementi maggiori risalgono come bolle verso le posizioni di indice piu’ alto del vettore; avremo che l’ elemento di valore massimo si porta in posizione n -1 = 9  nel nostro caso .

Nella seconda iterazione avremo che l’elemento massimo fra quelli rimasti raggiungera’ la posizione (n-2 esima) e cosi fino alla ultima iterazione dove avremo che ogni elemento avra’ raggiunto la posizione definitiva e quindi il vettore e’ ordinato. Notiamo che alla prima iterazione effettuiamo n -1 confronti alla seconda iterazione effettuiamo n -2 confronti alla terza effettuiamo n -3 confronti e cosi’ via fino alla 

(n-1 esima) iterazione dove si effettua un solo confronto.

In totale avremo [(n -1)+(n -2)+(n -3)+…+1]=[n*(n -1)/2] confronti.

Nel caso del nostro vettore VET con n=10, saranno necessari 45 confronti e di  scambi affinche’ lo si ordini. Tutto questo avviene considerando il caso peggiore, ossia un vettore con nessun elemento in posizione corretta, in altri termini un vettore ordinato in senso decrescente al crescere dell’indice dell’array. Se l'array ha un ordinamento casuale il numero di scambi e' imprecisato.

Vediamo allora il programma C che ordina in modo crescente, al crescere dell’indice dell’array, i valori di un vettore:

#include<stdio.h>

#define DIM  10

int main( )

{

  int  VET[DIM] = {2,  5,  6,  34,  11,  44,  33,  89,  68,  36 };

  int  i, iterazione, vecchio;

   printf (“\nStampa del vettore iniziale da ordinare”);

   for (i=0; i<DIM; i++)

   printf (“\n%d”, VET[i] );

     for (iterazione=1; iterazione<=DIM -1 ; iterazione++)  /*Iterazioni*/

     for (i=0;i<=DIM - iterazione -1 ; i++)  /*Passi*/

      if (VET[i] >VET[i+1] )   /*confronto*/

      {                                   /* scambio*/

       vecchio = VET[i];   

       VET[i] = VET[i+1];

        VET[i+1] = vecchio;

       }

printf (“\nStampa del vettore ordinato in senso ascendente\n”);

for (i=0;i<=DIM-1; i++)

printf (“\n%4d”,VET[i]);

printf (“\n”);

return 0;

}

Consideriamo un  esempio  grafico che mostra il comportamento dell’algoritmo bubble-sort.

 

Supponiamo di avere il seguente array di interi  int VET[4]={55,12,44,9} e di volerlo ordinare in senso crescente al crescere dell’ indice del vettore.

 

 

VET 

55	12	44	9
0	1	2	3

 

 

Iterazione 1

Passo 1)  confrontiamo 12 con 55 ; if(55>12) si ed allora li scambiamo di posto avremo quindi:

 

VET’

12

55

44

9

 

Passo 2) confrontiamo 55 con 44; if (55>44) si ed allora li scambiamo di posto

 

VET’’

12

44

55

9

 

Passo 3) confrontiamo 55 con 9; if(55>9) si ed allora li scambiamo di posto.

 

VET’’’

12

44

9

55

 

Abbiamo concluso cosi’ la prima iterazione ed abbiamo posizionato l’elemento massimo del vettore nella ultima posizione dell’array (n-1 esima).

Su questo indice e sull’elemento contenuto in corrispondenza di tale indice non si lavora piu’ nelle iterazioni successive.

VET’’’

12

44

9

55

 

Iterazione 2

 

Passo 1) confrontiamo il 12 con il 44; if(12>44) no ed allora tutto rimane come prima.

VET’’’’

12

44

9

55

 

Passo 2) confrontiamo il 44 con il 9; if (44>9) si ed allora li scambiamo di posto

 

VET’’’’’

12

9

44

55

 

Abbiamo concluso i passi della seconda iterazione e portato l’elemento massimo fra gli n-1 elementi su cui stavamo lavorando nella sua posizione corretta la n-2 esima.

Adesso sui due elementi ordinati non si lavora piu’ nelle successive iterazioni.

VET’’’’’

12

9

44

55

 

Iterazione 3

 

Passo 1) si confronta il 12 con il 9; if (12>9) si ed allora li scambiamo di posto

 

VET’’’’’’

9

12

44

55

 

 

Con questa iterazione si conclude l’ordinamento dell’array ed abbiamo l’array seguente ordinato in senso crescente al crescere degli indici.

 

VET

9

12

44

55

 

 

 

Esercizio

 

 

Ordinamento di altre strutture dati

 

Fino ad adesso abbiamo considerato due algoritmi che operavano l’ordinamento sugli array di interi, lo stesso si potrebbe fare se gli array fossero di tipo (char, float …); basterebbe soltanto cambiare il tipo di dati degli argomenti e delle variabili delle funzioni usate nell’ordinamento. Al fine di adattare gli algoritmi di ordinamento ad altre strutture dati, basta modificare il codice, in coerenza con la nuova struttura dati coinvolta nell’ordinamento, fermo restando che gli algoritmi rimangono quelli introdotti.

 

 

Bubble-sort interattivo

 

 

Ricerca di un elemento in un array di interi

 

Ci occuperemo soltanto di due tipi di ricerca la ricerca sequenziale e la ricerca binaria.

 

Ricerca sequenziale

 

Data una certa chiave (elemento da cercare), si vuole trovare tale elemento in un array di interi od in generale le informazioni relative a tale elemento in un insieme di elementi ( che possono essere tipi di dati quali le stringhe le strutture le liste  eccetera ..).

 

In genere questo tipo di ricerca si adotta quando l’array non e’ ordinato e consiste nello scandire tutto l’array e confrontare ogni suo elemento con la nostra chiave.

Si intuisce che la complessita’ o costo, nel caso peggiore, di un algoritmo che implementi la ricerca sequenziale e’ pari al numero di elementi dell’array ossia l’algoritmo ha un costo lineare con n.

 

Scriviamo adesso una funzione che ricerca un certo carattere in un array di caratteri di lunghezza nota, finche’ non e’ soddisfatto il confronto con una chiave specificata.

 

int ricerca_sequenziale(char *elemento, int cont, char chiave)

{

register int k; /*se puo’ memorizza k in un registro*/

for(k=0; k<cont; k++)

  if(chiave==elemento[k] )

    return(k); /* ritorna l’indice dove si trova la chiave cercata*/

 else return( -1); /*l’elemento non e’ stato trovato*/

}

 

notiamo che la se la chiave cercata e’ in ultima posizione o non esiste proprio l’array di caratteri elemento viene scandito fino in fondo, e questo dimostra che il costo della ricerca sequenziale nel caso peggiore e’ pari al numero n di elementi dell’array.

Nel caso medio la ricerca sequenziale effettua un numero di confronti (if (…)) pari ad n/2 e nel caso migliore 1 solo confronto: “elemento cercato si trovava in prima posizione nell’array”.

 

Se si hanno grandi quantita’ di dati, questo algoritmo diventa inefficiente, per il tempo che si impiegherebbe nel caso in cui l’elemento da cercare capiti in posizione finale nel posto in cui sono immagazzinati tali dati.

Si deduce da cio’ che bisogna adottare in tali casi altri tipi di algoritmi per effettuare la ricerca in tempi piu’ brevi.

 

 

Esercizio

 

 

Ricerca binaria

 

L’algoritmo di ricerca binaria si applica soltanto agli insiemi ordinati, secondo un determinato criterio.

 

Ricerca binaria in un array di numeri interi

 

Supponiamo di avere un array di nome  RB  costituito dai primi 15 numeri interi positivi.

 

RB

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

 

Se volessimo ricercare l’elemento 11 (chiave) nell’array RB ci comportiamo nel modo seguente:

 

Il numero da cercare si puo’ trovare in uno dei seguenti posti:

- elemento mediano dell’array ;

- nella meta’ a sinistra dell’elemento mediano;

- nella meta’ a destra dell’elemento mediano.

 

Quindi attraverso la ricerca binaria si confronta 11 con l’elemento mediano 8

if (11>=8)  si  allora sicuramente la nostra chiave 11 si trova nella meta’ a destra dell’elemento mediano del nostro array o coincide con l’elemento mediano stesso. Se coincide con l’elemento mediano abbiamo finito la ricerca, altrimenti, scartiamo in tale modo dalla ricerca la meta’ degli elementi, quelli a sinistra di 8.

Adesso troviamo il nuovo elemento mediano della sottometa’ dell'array a destra dell' elemento mediano che avevamo considerato prima.

 

RB’

9

10

11

12

13

14

15

 

Il numero da cercare si puo’ trovare nuovamente in uno dei seguenti posti:

elemento mediano dell’array ;

nella meta’ a sinistra dell’elemento mediano;

nella meta’ a destra dell’elemento mediano.

Confrontiamo il numero da cercare 11 con il nuovo elemento mediano, il 12 if(11>=12) no allora sicuramente l’elemento cercato coincide o con l’elemento mediano oppure con un elemento situato nella meta’ a sinistra di RB’. Visto che non coincide con l’elemento mediano cerchiamo nella sottometa’.

 

RB’’

9

10

11

 

Il numero da cercare si puo’ trovare nuovamente in uno dei seguenti posti:

elemento mediano dell’array ;

nella meta’ a sinistra dell’elemento mediano;

nella meta’ a destra dell’elemento mediano.

 

Confrontiamo il numero da cercare 11 con il nuovo elemento mediano, il 10 if(11>=10)  si  allora sicuramente l’elemento cercato coincide o con l’elemento mediano oppure con un elemento situato nella meta’ a destra di  RB’’.

 

RB’’’

11

 

Il numero da cercare si puo’ trovare nuovamente in uno dei seguenti posti:

elemento mediano dell’array ;

nella meta’ a sinistra dell’elemento mediano;

nella meta’ a destra dell’elemento mediano.

 

Confrontiamo il numero da cercare 11 con il nuovo elemento mediano, il 11 if(11>=11)  si  allora sicuramente l’elemento cercato coincide o con l’elemento mediano oppure con un elemento situato nella meta’ a destra di  RB’’’. In questo caso coincide con l’elemento mediano e quindi la ricerca e’ finita avendo trovato l’elemento che volevamo cercare.

 

Vediamo adesso di formalizzare meglio il metodo empirico descritto, applicandolo ad un generico array  a  di n numeri interi.

 

 

a

a0

a1

a2

a3

..

..

amed

..

..

..

an-2

an-1

 

Detto amed l’elemento mediano dell’array  a  avremo che il modo per calcolarlo potrebbe essere :  amed=n/2; ma in tale modo non riusciamo a calcolare l’indice dell’elemento centrale ogni volta che riduciamo gli elementi da confrontare; il metodo che funziona nel caso generale e’ il seguente:

 

amed= (estr_sup + estr_inf)/2:

 

estr_sup e’ l’estremo superiore dell’array mentre estr_inf e’ l’estremo inferiore dell’array.

Infatti ogni volta che si effettua un confronto abbiamo visto che viene eliminata una meta’ degli elementi dal proseguo della ricerca; per cui gli estremi inferiori e superiori cambiano di volta in volta e necessitano di essere aggiornati contestualmente.

 

Se la chiave x che stiamo cercando e’ presente nell’array a significa che deve essere compreso fra a[estr_inf] ed a[estr_sup] , di conseguenza necessitano di un aggiornamento in modo che venga rispettata la condizione di presenza dell’elemento x nell’array.

Introduciamo allora il seguente test: if( x>=a[amed] ).

Se questa condizione e’ vera, x stara’ nell’intervallo 

[amed ,estr_sup], quindi si aggiorna : estr_inf=amed; altrimenti estr_sup=amed;

questo procedimento deve essere sempre iterato fino a quando non risulti che (estr_inf +1 ) == estr_sup; in tal caso vuol dire che abbiamo controllato tutti gli elementi.

 

Descrizione discorsiva dell’algoritmo di ricerca binaria

 

1)    Definire l’array ed il valore cercato x

2)    Assegnare ai limiti dell’array le due variabili estr_inf ed estr_sup

3)    Calcolare la posizione mediana della rimanente porzione di array da esaminare

a)    Ripetere

b)    Se il valore cercato x e’ maggiore del valore corrente allora

c)     Aggiorna di conseguenza il limite inferiore

d)    Aggiorna di conseguenza il limite superiore

e)     Calcola di nuovo e per ogni passo l’elemento amed

4)    Se l’elemento a[amed]  e’ uguale all’elemento cercato x allora

Comunica di averlo trovato (restituisci ad es. l’indice dell’array)

Altrimenti

Comunica di non averlo trovato (restituisci ad es. -1)

 

Scriviamo adesso la versione in linguaggio C della funzione di ricerca binaria

 

int ricerca_binaria( int a[ ], int x, int n)

{ int estr_inf=0;

   int estr_sup=n-1;

   int amed ;

 

  while (estr_inf <= estr_sup)

  {

   amed= (estr_inf + estr_sup)/2;

   if( x>a[amed])

    estr_inf = amed+1;

  else if(x<a[amed])

    estr_sup = amed -1;

    else return (amed);

  }

 return -1;

}

 

La complessita’ dell’algoritmo di ricerca binaria dipende dal particolare elemento da ricercare.

Nel caso si cerchi l’elemento mediano, basta soltanto un solo confronto mentre se si cerca un elemento diverso da quello mediano bisogna effettuare un numero maggiore di confronti (il confronto rappresenta l’operazione dominante e quindi assimiliamo la complessita’ col numero di confronti).

Il caso peggiore si verifica quando l’elemento che si cerca non e’ presente nell’array.

Dopo k confronti la dimensione dell’array su cui effettuiamo la ricerca si riduce a n/(2^k); pertanto nel caso peggiore il numero di confronti coincide con il piu’ piccolo intero m che soddisfa la seguente relazione:

2^m>=n; da cui:

log 2 (2^m)>=log 2 n da cui:

m>=log 2 n

quindi non appena il numero di confronti m e’ maggiore di log 2  n  la ricerca termina; l'emme che verifica cio' e': m=P.i.i.(log2 n) +1 ; (dove P.i.i.( ) abbiamo indicato la parte intera inferiore dell'argomento fra parentesi tonde ).

Possiamo concludere dicendo che la complessita’ dell’algoritmo di ricerca binaria e’ funzione del logaritmo in base due di n.

 

Esempio

Avendo un array di 1025 elementi, ordinati in senso crescente, nel caso peggiore per trovare un elemento dell’array o per scoprire che non esiste, con la ricerca binaria, occorrono m=P.i.i.( log 2  1025 )+1 confronti ossia m=11 confronti.

 

Esercizio