Corso di Fondamenti di Informatica
                       Prof. P.G. Franciosa
                          a.a. 2000-2001

                a cura della prof.ssa Isabella Lari


Nel presente documento sono riportati i programmi C che implementano gli 
algoritmi di ordinamento, di ricerca binaria e di ricerca del k-mo elemento
che sono stati trattati durante il corso.

Per una descrizione degli algoritmi si possono consultare i seguenti testi:

"Guida al linguaggio C", A. Bellini, A. Guidi (per la ricerca binaria e il bubble sort);

"Introduzione agli algoritmi, vol. I", T.H. Cormen, C.E. Leiserson, R.L. Rivest
(per l'insertion sort, il selection sort, il mergesort, il counting sort e 
la selezione del k-mo elemento)

________________________________________________________________________________

1. Ricerca binaria iterativa

#include <stdio.h>
#include <conio.h>
#define NMAX 100

int main()
{
	int n,i,x,a,b,h,trovato;
	int v[NMAX];

	clrscr();
	/*legge la dimensione del vettore e il vettore*/
	printf("scrivi la dimensione del vettore: ");
	scanf("%d%",&n);
	i=0;
	while (i<n)
	{	printf("v[%d] = ",i);
		scanf("%d",&v[i]);
		i++;
	}
	while (1) {
		printf("scrivi l'elemento da cercare: ");
		scanf("%d",&x);
		if (x==0) break;
		a=0;
		b=n-1;
		trovato=0;
		while ((a<=b)&&(!trovato)) {
			h=(a+b)/2;
			if (x==v[h])
				trovato=1;
			else if (x<v[h])
				b=h-1;
			else
				a=h+1;
		}
		if (trovato)
			printf("elemento trovato in posizione %d\n",h);
		else
			printf("elemento non trovato\n");
	}
	return(0);
}

___________________________________________________

2. Ricerca binaria ricorsiva

#include <stdio.h>
#include <conio.h>
#define NMAX 100

int binaria(int *vett, int a, int b, int x)
{ 	int h;
	if (a>b)
		return(-1);
	else  {
		h=(a+b)/2;
		if (x==vett[h])
			return(h);
		else if (x<vett[h])
			return(binaria(vett,a,h-1,x));
		else
			return(binaria(vett,h+1,b,x));
	}
}


int main()
{
	int n,i,x,posizione;
	int v[NMAX];

	clrscr();
	/*legge la dimensione del vettore e il vettore*/
	printf("scrivi la dimensione del vettore: ");
	scanf("%d%",&n);
	i=0;
	while (i<n)
	{	printf("v[%d] = ",i);
		scanf("%d",&v[i]);
		i++;
	}
	while (1) {
		printf("scrivi l'elemento da cercare: ");
		scanf("%d",&x);
		if (x==0) break;
		posizione=binaria(v,0,n-1,x);
		if (posizione != -1)
			printf("elemento trovato in posizione %d\n",posizione);
		else
			printf("elemento non trovato\n");
	}
	return(0);
}

___________________________________________________________

3. Selection sort

#include <stdio.h>
#include <conio.h>

void leggi_vettore(int *n,int *vett);
void scambia(int *a, int *b);
void stampa_vettore(int n, int *vett);

main()
{       int v[100];
	int n,i,j,kmax,max;
	clrscr();
	leggi_vettore(&n,v);
	for (i=n-1;i>0;i--) {
		max=v[0];
		kmax=0;
		for (j=1;j<=i;j++) {
			if (v[j]>max) {
				max=v[j];
				kmax=j;
			}
		}
		if (kmax!=i)
			scambia(&v[kmax],&v[i]);
	}
	stampa_vettore(n,v);
	getch();
}


void leggi_vettore(int *n, int *vett)
{       int i;
	printf("scrivi la dimensione del vettore (<=100): ");
	scanf("%d",n);
	for (i=0;i<*n;i++) {
		printf("v[%d] = ",i);
		scanf("%d",&vett[i]);
	}
}

void scambia(int *a, int *b)
{	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

void stampa_vettore(int n, int *vett)
{       int i;
	printf("\n\n");
	for (i=0;i<n;i++)
		printf("v[%d] = %d\n",i,vett[i]);
}
_________________________________________________

4. Insertion sort

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

void leggi_vettore(int *n,int *vett);
void stampa_vettore(int n, int *vett);

main()
{   int v[100];
	int n,i,j,app;
	clrscr();
	leggi_vettore(&n,v);
	stampa_vettore(n,v);

	for (i=1;i<n;i++) {
		app=v[i];
		j=i;
		while ((j>0) && (app<v[j-1])) {
			v[j]=v[j-1];
			j--;
		}
		if (j!=i)
			v[j]=app;
	}

	stampa_vettore(n,v);
	getch();
}


void leggi_vettore(int *n, int *vett) /*genera un vettore casuale*/
{   int i;
	randomize();
	*n=random(101);
	for (i=0;i<*n;i++)
		vett[i]=random(1000);
}

void stampa_vettore(int n, int *vett)
{       int i;
	printf("\n\n");
	for (i=0;i<n;i++)
		printf("v[%d] = %d\n",i,vett[i]);
}

_________________________________

5. Bubble sort

#include <stdio.h>
#include <conio.h>

void leggi_vettore(int *n,int *vett);
void scambia(int *a, int *b);
void stampa_vettore(int n, int*vett);

main()
{       int v[100];
	int n,i,j,p,k,m;
	clrscr();
	leggi_vettore(&n,v);
	m=n;
	do {
		k=0;
		for (i=0;i<m-1;i++) {
			if (v[i]>v[i+1]) {
				scambia(&v[i],&v[i+1]);
				k=1;
				p=i+1;
			}
		}
		m=p;
	}
	while(k==1);
	stampa_vettore(n,v);
	getch();
}


void leggi_vettore(int *n, int *vett)
{       int i;
	printf("scrivi la dimensione del vettore (<=100): ");
	scanf("%d",n);
	for (i=0;i<*n;i++) {
		printf("v[%d] = ",i);
		scanf("%d",&vett[i]);
	}
}

void scambia(int *a, int *b)
{	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

void stampa_vettore(int n, int *vett)
{       int i;
	printf("\n\n");
	for (i=0;i<n;i++)
		printf("v[%d] = %d\n",i,vett[i]);
}

___________________________________________

6. Merge sort

#include <stdio.h>
#include <conio.h>

void leggi_vettore(int *n,int *vett);
void stampa_vettore(int n, int *vett);
void merge(int a1, int a2, int b2, int *vett);
void mergesort(int a, int b, int *vett);


main()
{       int v[100];
	int n;
	clrscr();
	leggi_vettore(&n,v);
	mergesort(0,n-1,v);
	stampa_vettore(n,v);
	getch();
}


void leggi_vettore(int *n, int *vett)
{       int i;
	printf("scrivi la dimensione del vettore (<=100): ");
	scanf("%d",n);
	for (i=0;i<*n;i++) {
		printf("v[%d] = ",i);
		scanf("%d",&vett[i]);
	}
}



void stampa_vettore(int n, int *vett)
{       int i;
	printf("\n\n");
	for (i=0;i<n;i++)
		printf("v[%d] = %d\n",i,vett[i]);
}


void merge(int a1, int a2, int b2, int *vett)
{    int i1, i2,i,j;
     int app[100];

     i1=a1;i2=a2;i=0;
     do
	 	if (vett[i1]<vett[i2])
			app[i++]=vett[i1++];
	 	else
			app[i++]=vett[i2++];
	 while ((i1<=a2-1) && (i2<=b2));

     for (j=i;j<=b2-a1+1;j++)
		if (i1>=a2)
			app[j]=vett[i2++];
	 	else
			app[j]=vett[i1++];
	 
	 i=0;
	 for (j=a1;j<=b2;j++)
		vett[j]=app[i++];

}


void mergesort(int a, int b, int *vett)
{       int medio;
		if (a<b){
			medio=(a+b)/2;
			mergesort(a,medio,vett);
			mergesort(medio+1,b,vett);
			merge(a,medio+1,b,vett);
		}
}


___________________________________________

7. Counting sort (ordina vettori con elementi interi nell'intervallo [0,99])

#include <stdio.h>
#include <conio.h>

void leggi_vettore(int *n,int *vett);
void stampa_vettore(int n, int *vett);

main()
{   int a[100],b[100],c[100];
	int n,i,j;
	clrscr();
	leggi_vettore(&n,a);
	/* si ipotizza che gli elementi
	 del vettore siano interi nell'intervallo [0,99]*/

	for (j=0;j<100;j++)
		c[j]=0;

	for (i=0;i<n;i++)
		c[a[i]]=c[a[i]]+1;

	for (j=1;j<100;j++)
		c[j]=c[j-1]+c[j];

	for (i=n-1;i>=0;i--){
		b[c[a[i]]-1]=a[i];
		c[a[i]]=c[a[i]]-1;
	}
	stampa_vettore(n,b);
	getch();
}

void leggi_vettore(int *n, int *vett)
{       int i;
	printf("scrivi la dimensione del vettore (<=100): ");
	scanf("%d",n);
	for (i=0;i<*n;i++) {
		printf("v[%d] = ",i);
		scanf("%d",&vett[i]);
	}
}

void stampa_vettore(int n, int *vett)
{       int i;
	printf("\n\n");
	for (i=0;i<n;i++)
		printf("v[%d] = %d\n",i,vett[i]);
}

___________________________________________


8. Selezione del k-mo elemento (versione iterativa)


#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

void leggi_vettore(int *n,int *vett);
void scambia(int *p, int *q);
void stampa_vettore(int n, int *vett);
int partition(int *vett, int a, int b);

main()
{       int v[100];
	int n,a,b,k,q;
	clrscr();
	leggi_vettore(&n,v);
	stampa_vettore(n,v);

	printf("scrivi quale elemento vuoi cercare: ");
	scanf("%d",&k);

	a=0;
	b=n-1;
	do   {
		q=partition(v,a,b);
		if (q<k-1)
			a=q+1;
		else if (q>k-1)
			b=q-1;
		else
		       break;
	      }
	while (a < b);

	stampa_vettore(n,v);
	printf("\n il %d elemento e' %d: \n",k,v[k-1]);

	getch();
}

	
void leggi_vettore(int *n, int *vett)
{       int i;
	randomize();
	*n=8;
	for (i=0;i<*n;i++)
		vett[i]=random(100);
}

void scambia(int *p, int *q)
{	int temp;
	temp=*p;
	*p=*q;
	*q=temp;
}


void stampa_vettore(int n, int *vett)
{       int i;
	printf("\n\n");
	for (i=0;i<n;i++)
		printf("v[%d] = %d\n",i,vett[i]);
}



int partition(int *vett, int a, int b)
{
	int i,j,q,x;
	x=vett[a];
	i=a+1;
	j=b;
	while (i<j)  {
		while ((i<j) && (vett[i]<=x))
			i++;
		while ((i<j) && (vett[j]>x))
			j--;
		if (i<j)
			scambia(&vett[i],&vett[j]);
	}
	if (x<vett[i])
		q=i-1;
	else
		q=i;
	scambia(&vett[a],&vett[q]);
	return(q);
}

/*versione randomizzata di partition

int partition(int *vett, int a, int b)
{
	int i,j,q,x,s;
	randomize;
	s=random(n);
	scambia(&vett[s],&vett[a]);
	x=vett[a];
	i=a+1;
	j=b;
	while (i<j)  {
		while ((i<j) && (vett[i]<=x))
			i++;
		while ((i<j) && (vett[j]>x))
			j--;
		if (i<j)
			scambia(&vett[i],&vett[j]);
	}
	if (x<vett[i])
		q=i-1;
	else
		q=i;
	scambia(&vett[a],&vett[q]);
	return(q);
} */

___________________________________________


9. Selezione del k-mo elemento (versione ricorsiva)



#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

void leggi_vettore(int *n,int *vett);
void scambia(int *p, int *q);
void stampa_vettore(int n, int *vett);
int partition(int *vett, int a, int b);
int select(int *vett, int p, int r, int k);


main()
{   int v[100];
	int n,k;
	clrscr();
	leggi_vettore(&n,v);
	stampa_vettore(n,v);

	printf("scrivi quale elemento vuoi cercare: ");
	scanf("%d",&k);

	printf("\n il %d elemento e' %d: \n",k,select(v,0,n-1,k));
	stampa_vettore(n,v);

	getch();
}

	
void leggi_vettore(int *n, int *vett)
{       int i;
	randomize();
	*n=8;
	for (i=0;i<*n;i++)
		vett[i]=random(100);
}

void scambia(int *p, int *q)
{	int temp;
	temp=*p;
	*p=*q;
	*q=temp;
}


void stampa_vettore(int n, int *vett)
{       int i;
	printf("\n\n");
	for (i=0;i<n;i++)
		printf("v[%d] = %d\n",i,vett[i]);
}



int partition(int *vett, int a, int b)
{
	int i,j,q,x;
	x=vett[a];
	i=a+1;
	j=b;
	while (i<j)  {
		while ((i<j) && (vett[i]<=x))
			i++;
		while ((i<j) && (vett[j]>x))
			j--;
		if (i<j)
			scambia(&vett[i],&vett[j]);
	}
	if (x<vett[i])
		q=i-1;
	else
		q=i;
	scambia(&vett[a],&vett[q]);
	return(q);
}


int select(int *vett, int p, int r, int k)
{	int q;
	if (p==r)
		return(vett[p]);
	else  {
		q=partition(vett,p,r);
		if (q<k)
			return(select(vett,q+1,r,k));
		else if (q>k)
			return(select(vett,p,q-1,k));
		else
			return(vett[q]);
	}
}