css

Algoritmi di Ordinamento e Ricerca

Gli algoritmi di ordinamento permettono di ordinare in modo crescente o decrescente gli array.

Gli algoritmi di ricerca permettono di individuare all'interno di un array un elemento dato.

Selection sort (1)

Se prendiamo in considerazione un array di N elementi, con l'indice che varia da 1 a N-1 , la Selection Sort confronta ogni elemento (i) con tutti quelli di indice superiore (j=i+1), e ne scambia il contenuto quando il valore dell'elemento preso in considerazione risulta maggiore di quello con cui viene confrontato. Esempio:

for(i=0;i<N-1;i++)
    for(j=i+1;j<N;j++)
       if(array[i] > array[j])
          temp=array[i];
          array[i]=array[j];
          array[j]=temp;

Funzionamento:

selection sort
  1. Controllo tutto l'array, dall'elemento 0 all'elemento N-1;
  2. Cerco l'elemento più piccolo;
  3. Scambio gli elementi, mettendo in N[0] il più piccolo;
  4. Cerco nuovamente l'elemento più piccolo e lo metto in N[1], scambiandolo con quello già presente;
  5. Eseguo lo stesso procedimento fino all'ultimo elemento;

VANTAGGI:

  • L'algoritmo Selection Sort è più facile da implementare e da capire, difatti richiede un minore numero di righe di codice e una struttura più semplice;
  • Richiede un ridotto utilizzo di memoria;
  • è adatto nelle situazioni in cui non è necessaria una grande complessità computazionale;
  • è decisamente più veloce di altri tipi di ordinamenti;

SVANTAGGI:

  • L'algoritmo Selection Sort è inadatto ad array di grandi dimensioni (in questi casi sono preferibili altri algoritmi come il Quick Sort);
  • Se gli elementi dell'array sono già parzialmente ordinati questo algoritmo non è considerabile adatto;

Selection sort (2)

Codice del funzionamento dell'algoritmo di ordinamento per selezione, secondo metodo:

for(i=0; i<numElem -1; i++)
    posizMin = i;
    for(j=i+1; j<numElem; j++)
        if(vett[j] < vett[posizMin])
            posizMin = j;
        temp = vett[posizMin];
        vett[posizMin] = vett[i];
        vett[i] = temp;





Funzionamento →

selection sort

VANTAGGI:

  • è uno degli algoritmi di ordinamento più semplici capire.
  • è efficiente per ordinare piccole liste
  • è un algoritmo stabile, ovvero mantiene l'ordine relativo degli elementi con chiavi uguali.

SVANTAGGI:

  • diventa molto inefficiente per ordinare grandi liste.
  • ha una complessità di tempo di O(n^2), il che significa che il tempo di esecuzione aumenta rapidamente all'aumentare della dimensione della lista.
  • non è adatto per ordinare liste parzialmente ordinate, poichè esegue comunque un numero elevato di confronti e scambi.

Bubble sort

Questo algoritmo confronta 2 elementi alla volta e gli scambia di posto se necessario facendo "risalire" gli elementi più grandi verso le posizioni corrette.

scambio = 1;
while(scambio)
    scambio=0;
    for(i=0; i<numElem-1; i++)
        if(vett[i] > vett[i+1])
           scambio = 1;
           temp=vett[i];
           vett[i] = vett[i+1];
           vett[i+1] = tmp;

La versione ottimizzata utilizza anche una variabile k contenente l'ultima posizione in cui è avvenuto uno scambio.

k = numElem -1;
scambio = 1;
while(scambio)
    sup = k;
    scambio=0;
    for(i=0; i<sup-1; i++)
        if(vett[i] > vett[i+1])
           scambio = 1;
           k = i;




Funzionamento →

selection sort

VANTAGGI:

  • è semplice da scrivere
  • facile da implementare

SVANTAGGI:

  • è adatto per l'insegnamento accademico ma non viene molto usato per le applicazioni reali: infatti, esegue n^2 passaggi di elaborazione per un numero n di elementi da ordinare, risultando inadatto per applicazioni reali.

Algoritmi di Ricerca

Problema= "dato un insieme L di n elementi e un elemento x verificare se questo appartiene a L"

1) Ricerca sequenziale o lineare

Si parte dal primo elemento e si esamina ogni elemento fino a quando non trovo la posizione dell'elemento cercato oppure fino a quando non termino tutte le verifiche da fare senza trovare l'elemento cercato. L'algoritmo può essere usato sia in un vettore ordinato che non ordinato.

int i;
for(i=0; i<numElem; i++)
    if(elem == vett[i])
        return i;
return -1;




Funzionamento →

selection sort

2) Ricerca binaria o dicotomica

L'algoritmo inizia la ricerca non dall'inizio ma da metà confrontando così il valore ricercato con quello trovato con la ricerca: se l'uguaglianza risulta vera si termina l'esecuzione, mentre se è inferiore la ricerca viene ripetuta nello stesso modo per gli elementi precedenti, invece se è superiore la ricerca viene effettuata per gli elementi successivi. Questo algoritmo ha il vantaggio di effettuare meno confronti, infatti effettua al massimo log2n operazioni per n elementi ma ha lo svantaggio di poter essere usato solo in un vettore ordinato.

int m= (i+f)/2;
c++;
printf("Iterazione %d intervallo ( %d , %d ) %d \n", c, i, f, m );
if (f<i)
    return -1;
if (v[m]>n)
    return ricerca(v,n,i,m-1);
else if (v[m]<n)
    return ricerca(v,n,m+1,f);
else
    return m;




Funzionamento →

selection sort