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(j=i+1;j<N;j++)
if(array[i] > array[j])
temp=array[i];
array[i]=array[j];
array[j]=temp;
Funzionamento:
- Controllo tutto l'array, dall'elemento 0 all'elemento N-1;
- Cerco l'elemento più piccolo;
- Scambio gli elementi, mettendo in N[0] il più piccolo;
- Cerco nuovamente l'elemento più piccolo e lo metto in N[1], scambiandolo con quello già presente;
- 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:
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 →
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.
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.
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 →
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.
for(i=0; i<numElem; i++)
if(elem == vett[i])
return i;
return -1;
Funzionamento →
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.
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 →
