Ordinamento e Ricerca sugli Array in C

Introduzione
Le strutture dati in linguaggio C sono molteplici nella lezione precedente è stato introdotto l’array o vettore una struttura dati omogenea che è identificata da un nome collettivo e i cui elementi sono individuati mediante un indice. E’ una struttura dati temporanea ovvero i dati sono memorizzati in memoria RAM ma è il punto il punto di partenza di molti problemi che coinvolgono una grande quantità di dati.

Argomenti

Complessità computazionale
Algoritmo di ordinamento per selezione
Algoritmo di ordinamento a bolle
Algoritmo di ricerca binaria
Caso di studio il Codice dei nostri algoritmi
Video della lezione

Complessità computazionale

Finora sono stati scritti algoritmi e programmi senza valutare se questi ultimi sono ottimizzati.
Tale valutazione è molto complessa, poiché richiede delle nozioni molto ampie di matematica e della teoria della complessità.
Il problema è posto quando la dimensione dell’input che chiamiamo N ovvero il numero dei dati coinvolti nell’elaborazione dell’algoritmo cresce e diventa molto grande per intenderci N ➔ ∞ che indica che N tende all’infinito e diventa molto grande anzi “enorme”.
In questo caso il tempo di esecuzione dell’algoritmo pesa sull’elaborazione complessiva e non poco.
E’ possibile fare una stima mediante la teoria degli algoritmi e lo studio della complessità che dimostra che il tempo di elaborazione può essere stimato come ordine di grandezza e non come tempo preciso (questo perché il tempo assoluto come misura dipende dal tipo di architettura hardware, dal sistema operativo, dal programma e dal linguaggio di programmazione utilizzato). E’ più importante stimare l’ordine di grandezza che da un’idea di quanto potrebbe impiegare un calcolatore ad eseguire l’algoritmo in funzione della dimensione dell’input.
Tale stima si indica con la notazione “O grande” che indica appunto questo parametro ed è una funzione di N. Quando affermiamo che un algoritmo ha una complessità O(N) stiamo dicendo che il tempo di esecuzione cresce come un tempo lineare di N che è l’input. Sarebbe un ottimo risultato. Se invece siamo fortunati e il nostro algoritmo ha una complessità O(1) vuol dire che il tempo è costante ed è indipendente dalla dimensione dell’Input.
Molto spesso succede che il tempo di esecuzione è funzione di O(N²) e non è un risultato ottimo in quanto vuol dire che se N=10 il tempo è stimato su un ordine di grandezza di 100.

Algoritmo di ordinamento per selezione

L’ordinamento di un array riveste la sua importanza poiché in seguito eseguire una ricerca su un array ordinato è molto più performante che su una struttura non ordinata. Di norma gli ordinamenti sono eseguiti quando nell’array sono inseriti o sostituiti o cancellati dati.
Le ricerche invece sono molto più frequenti e quindi avere una ricerca ottimizzata rappresenta un grosso vantaggio.
Il primo ordinamento che si vuole esaminare è quello per selezione.
Immaginiamo un array X[] = {3;10;5;2;-3;10;8;1;4,-2} costituito da 10 elementi.
L’idea più semplice per l’ordinamento (in questo caso crescente) in fissare un elemento con un indice I che varia da 0 a N-2 e far muovere un indice J che va da I+1 a N-1 ovvero il successivo di I fino all’ultimo elemento.
Esempio:
X[] = {3;10;5;2;-3;10;8;1;4,-2}
Confronto il primo valore con tutti i successivi se è maggiore scambiamo gli elementi:
X[] = {2;10;5;3;-3;10;8;1;4,-2}
X[] = {-3;10;5;3;2;10;8;1;4,-2}
X[] = {-3;10;5;3;2;10;8;1;4,-2} non sono eseguiti scambi in quanto -3 è il minimo dell’array. L’indice I passa da 0 a 1 e J partirà da 2 a N-1.
Quindi nel successivo ciclo interno il primo elemento quello con I=0 non viene considerato.
X[] = {-3;10;5;3;2;10;8;1;4,-2}
Nel confronto scambio ogni volta che l’elemento di posto J è più piccolo di quello fissato in questo caso:
X[] = {-3;5;10;3;2;10;8;1;4,-2}
X[] = {-3;5;3;10;2;10;8;1;4,-2}
X[] = {-3;5;3;10;2;10;8;1;4,-2}
X[] = {-3;2;3;10;5;10;8;1;4,-2}
X[] = {-3;2;3;10;5;10;8;1;4,-2}
X[] = {-3;-2;3;10;5;10;8;2;4,1}
Quindi in questa seconda serie di confronto il valore -2 è il secondo numero più piccolo presente nell’array e quindi nella serie successiva non si considera.
X[] = {-3;-2;3;10;5;10;8;2;4,1}
In base a questo si comprende che sono necessari due cicli uno sull’indice I che va da zero a N-2 e l’altro su J che va da I+1 a N-1. L’algoritmo terminerà quando sarà necessario confrontare il penultimo elemento con l’ultimo.
L’algoritmo ha il seguente pseudocodice:
inizio
for i= 0 to n-2 do:
for j=i+1 to n-1 do
if (x[i]>x[j])
tmp ← x[I]
x[i] ← x[j]
x[j] ← tmp
fine se
exit for j
exit for i
fine
Nell’algoritmo il significato è molto semplice: la variabile tmp è utilizzata per lo scambio fra l’elemento x[i] e l’elemento x[j] ogni volta che l’elemento di posizione j è minore dell’elemento di posizione i.
La complessità dell’algoritmo essendo presente un doppio ciclo for prevede (N-1)*(N-I+1) che al crescere di N può essere stimato in O(N²).

Ordinamento a bolle

Nell’ordinamento a bolle sono confrontati fra loro gli elementi adiacenti e nel caso di confronto con esito positivo (l’elemento I+1 è più piccolo dell’elemento I) si procede allo scambio. Alla fine di una prima serie di scambi nel caso di ordinamento crescente il maggiore sarà collocato in ultima posizione nell’array e si ripeterà l’algoritmo escludendo il massimo valore ottenuto in precedenza. In questo modo la dimensione dell’array diminuisce ad ogni ciclo di scambi. Quando non si effettueranno più scambi il vettore sarà ordinato.
A titolo di esempio riprendiamo l’array X:
X[] = {3;10;5;2;-3;10;8;1;4,-2}
X[] = {3;5;10;2;-3;10;8;1;4,-2}
X[] = {3;5;10;2;-3;10;8;1;4,-2}
X[] = {3;5;2;10;-3;10;8;1;4,-2}
X[] = {3;5;2;-3;10;10;8;1;4,-2}
X[] = {3;5;2;-3;10;10;8;1;4,-2}
X[] = {3;5;2;-3;10;8;10;1;4,-2}
X[] = {3;5;2;-3;10;8;10;1;4,-2}
X[] = {3;5;2;-3;10;8;1;10;4,-2}
X[] = {3;5;2;-3;10;8;1;4;10,-2}
X[] = {3;5;2;-3;10;8;1;4;10,-2}
X[] = {3;5;2;-3;10;8;1;4;-2,10} il primo valore maggiore è nell’ultima posizione.
L’array da considerare nella nuova serie di scambi è pertanto senza l’ultimo elemento ed è:
X[] = {3;5;10;-3;10;8;1;4;-2,10}
Il ciclo di scambio riparte con J che varia da 0 a N-2 e il primo scambio è:
X[] = {3;5;2;-3;10;8;1;4;-2,10}
X[] = {3;5;2;-3;8;10;1;4;-2,10} e così via.
L’algoritmo è sempre con complessità O(N²) ma nel caso migliore potrebbe scendere ad un tempo lineare se l’array è abbastanza ordinato.
L’algoritmo in pseudo-codice è:
inizio
j ← n
flag ← true
while (flag=true)
flag ← false
for i=0 to j-1 do
if (x[i]>x[i+1])
flag ← true
tmp ← x[i]
x[i] ← x[j]
x[j] ← tmp
fine se
fine for i
j ← j-1
fine while
fine
L’algoritmo prevede l’uso di una variabile flag che determina se sono stati effettuati durante i confronti gli scambi. Se non sono stati effettuati scambi il ciclo while termina poiché l’array risulta ordinato. Ad ogni ciclo for la dimensione dell’array j diminuisce da N fino ad eventualmente diventare j=1 per confrontare nell’utlimo ciclo il primo e il secondo elemento dell’array (e in questo caso vorrebbe dire che il vettore o array era molto disordinato).

Link di affiliazione

Ricerca Binaria o Dicotomica

La ricerca binaria è un algoritmo molto efficiente che è possibile su un array di elementi ordinato (il tipo di ordinamento non ha importanza).
E’ basato sul concetto di suddividere l’array in sub array sempre più piccoli ove eventualmente individuare l’elemento da cercare richiesto dall’utente come dato di input al problema.
Sempre con un array ordinato di 10 elementi interi:
X{}={1; 2; 3; 5; 7; 12; 20; 50; 102; 104}
L’elemento da cercare è e=20 che dall’array è posizionato ad un valore I=6).
L’algoritmo prevede di impostare tre indici supplementari inizialmente
inf←0; sup←N-1=9 e centro ← (intero)((inf+sup)/2)=4 (arrotondamento per difetto all’intero inferiore).
Quindi

X{}={1; 2; 3; 5; 7; 12; 20; 50; 102; 104}
In verde x[inf], in rosso x[centro] e in arancio x[sup];
Ora se x[centro]=e allora l’elemento è stato individuato e termina l’algoritmo altrimenti se x[centro]<e ad sup←centro+1 altrimenti inf←centro+1.
Nel nostro caso
x[centro]=7 < 20 e quindi inf← centro+1=5; suo rimane invariato e centro diventa (intero)(inf+sup)/2=7 e quindi
X{}={1; 2; 3; 5; 7;12; 20; 50; 102; 104}
e quindi ora x[centro]=50 non è 20 ma è maggiore di 20 e quindi:
inf←5; sup←centro-1=6 e centro←5
e quindi il sub array è:
X{}={1; 2; 3; 5; 7;12; 20; 50; 102; 104}
Ora x[centro]=e e l’algoritmo termina avendo individuato l’elemento in posizione 6. Se non trova l’elemento un flag logico indicherà all’utente mediante un messaggio che l’elemento non è stato trovato.
La complessità di questo algoritmo è O(log₂N) che è una funzione logaritmica in base 2 che cresce molto più lentamente di una funzione lineare e ancora meno di una funzione quadratica.
Nella sostanza quando N=2²⁰ il tempo di esecuzione è della grandezza di 20 un tempo ottimo. Ovviamente per l’ordinamento occorre individuare ordinamenti più efficienti quali “Merge Sort” o “Quick Sort” che saranno trattati molto avanti dopo aver compreso i concetti sulla ricorsione.
L’algoritmo è pertanto:
inizio
leggi e
inf ← 0
sup ← n-1
flag ← false
while (inf <=sup) and (flag=false)
centro ← (inf+sup)/2
if (x[centro]=e)
flag ← true
pos ← centro
else
if (e <x[centro]
sup ← centro-1
else inf ← centro+1
fine while
if (flag) scrivi “element trovato ! In posizione:”, pos
else scrivi “non trovato !”
fine

Caso di studio

Il codice C di questi algoritmi e degli algoritmi della lezione precedente sono strutturati a sotto programmi alcuni sono commentati. Puoi de-commentare per provare i vari algoritmi.

#include <stdio.h>
void carica(int x[], int l);
int cerca(int x[],int l, int z);
void ordinaselezione(int x[],int l);
void stampa(int x[],int l);
void ordinabolle(int x[],int l);
int dicotomica(int x[],int l, int e);
//void ordinabolle(int x[],int l);
//bool ricbinaria(int x[], int l, int e);
main()
{
	int n,inc;
	int pos;
	printf("Dimensione array:");
	scanf("%d",&n);
	int vet[n];
	int x,p;
	carica(vet,n);
	//printf("\n Inserisci il valore da cercare:");
	//scanf("%d",&inc);
	//pos=cerca(vet,n,inc);
	//if (pos!=-1)
	//	printf("\nHo trovato elemento in posizione:%d:",pos);
	//else
	//	printf("\n Non ho trovato elemento !:\n");
	stampa(vet,n);
	//ordinaselezione(vet,n);
	ordinabolle(vet,n);
	stampa(vet,n);
	printf("\n Inserisci elemento da cercare:");
	scanf("%d",&x);
	p=dicotomica(vet,n,x);
	if (p==-1)
		printf("\n Elemento non trovato !");
	else
		printf("\n Ho trovato elemento in posizione:\t%d\n",p+1);
	return;
}
void carica(int x[], int l)
{
	int k;
	for (k=0;k<l;k++)
	{
		printf("\n Inserisci elemento dell'array numero:%d:-->",k+1);
		scanf("%d",&x[k]);
	}
}
void stampa(int x[],int l)
{
	int i;
	printf("Vettore:\n");
	for (i=0;i<l;i++)
		{
			printf("%d\t",x[i]);
		}
		printf("\n");
}
int cerca(int x[],int l, int z)
{
	int p=-1;
	int k=0;
	int flag=0;
	while ((k<l)&&(flag==0))
	{
		if (x[k]==z)
			{
				p=k;
				flag=1;
			}
		k++;
	}
	return p;
}
void ordinaselezione(int x[],int l)
{
	int i,j;
	int tmp;
	for (i=0;i<l-1;i++)
			for (j=i+1;j<l;j++)
				if (x[i]>x[j])
				{
					tmp=x[i];
					x[i]=x[j];
					x[j]=tmp;
					}
}
void ordinabolle(int x[],int l)
{
	int flag=1;
	int i,j;
	int tmp;
	j=l;
	while (flag==1)
	{
		flag=0;
		for (i=0;i<j-1;i++)
			{
			if (x[i]>x[i+1])
				{
					flag=1;
					tmp=x[i];
					x[i]=x[i+1];
					x[i+1]=tmp;
				}
			}
			j--;
	}
}
int dicotomica(int x[],int l, int e)
{
	int centro,inf,sup;
	int flag=0;
	inf=0;
	int pos=-1;
	sup=l-1;
	while ((inf <=sup)&&(flag==0))
	{
		centro=(inf+sup)/2;
		printf("Sup: %d, Inf: %d, Centro:%d\n",sup,inf,centro);
		if (x[centro]==e)
		{
			flag=1;
			pos=centro;
		}
		else{
		if (e<x[centro])
			sup=centro-1;
		else inf=centro+1;}
	}
	return pos;
}