Algoritmi di Ordinamento

Autore: Santo Patti

In questa sezione sono implementati in c alcuni degli algoritmi di ordinamento più noti.

Complessità nel caso migliore O(n), nel caso peggiore O(n²)

int insertionsort(float *A, int length)
 
{
	if (length<=0) return 1;
 
	float key;
	int i,j;
	for (j=1; j < length; j++)
	{
		key=A[j];
		i=j-1;
		while ((i>=0)&&(A[i]>key))
			A[i+1]=A[i--];
		A[i+1]=key;
	}
	return 0;
}

Complessità nel caso migliore O(nlogn), nel caso peggiore O(nlogn)

void merge(float *AV, int p, int q, int r)
{
/* Crea il vettore ordinato risultato ponendo via via il
 * numero più piccolo che si trova in cima ad uno dei due
 * array di input */
 
 
	float vect[maxvect]; //array temporaneo
	int bx=0;	  //puntatore all'array vect
	int cx=p;	  //puntatore al primo array AV[p..q]
	int dx=q+1;	  //puntatore al secondo array AV[q+1..r]
 
	// creo l'array ordinato in vect!
 
	while ((cx <= q )&&(dx <= r))
	{
		if (AV[cx] < AV[dx]) 
			vect[bx++]=AV[cx++];
		else
			vect[bx++]=AV[dx++];
	}
	// A questo punto o il primo o il secondo array è completamente vuoto!
	while (cx <= q)
		vect[bx++]=AV[cx++];
	while (dx <= r)
		vect[bx++]=AV[dx++];
	// qui copiamo il nuovo array al suo posto
	for (cx=0; cx<bx; cx++)
		AV[cx+p]=vect[cx];
}
 
void mergesort(float *A, int p, int r)
 
{
	if (p<r)
	{
		int q=((p+r)/2);
		mergesort(&A[0], p, q);
		mergesort(&A[0], q+1, r);
		merge(&A[0], p ,q ,r);
	}
}

Complessità nel caso migliore O(nlogn), nel caso peggiore O(nlogn).

void quicksort(float *A, int p, int r)
{
	if (p<r)
	{
		int q=partition(&A[0],p,r);
		quicksort(&A[0],p,q);
		quicksort(&A[0],q+1,r);
	}	
}
 
int partition(float *A, int p, int r)
{
	float x;
	int i,j;
	x=A[p];
	i=p-1;
	j=r+1;
 
	for (;;)
	{
		do
			j--;
		while ((A[j]>x)&&(j>p));
 
		do
			i++;
		while ((A[i]<x)&&(i<r));
 
		if (i<j) xchange(&A[i],&A[j]);
		else return j;
	}
}
 
void xchange(float *x, float *y)
{
	float tmp=*x;
	*x=*y;
	*y=tmp;
}

Complessità nel caso migliore O(n+2^k), nel caso peggiore O(n+2^k).

int chk(int *A, int n)
{
	int j;
	for (j=0; j < n; j++)
		if (A[j]<1) return 0;
	return 1;
}
 
int countings(int *A, int lA, int *B, int k)
{
	if (!chk(&A[0],lA)) return 1;
	int i;
 
	int *C = new int (k); //Allocazione dinamica dell'array C
	for (i=0; i < k; i++)
		C[i]=0;
 
	for (i=0; i < lA; i++)
		C[A[i]-1]=C[A[i]-1]++;
 
	for (i=1; i < k; i++)
		C[i]=C[i] + C[i-1];
 
	for (i=lA-1; i>-1; i--)
	{
		B[C[A[i]-1]-1]=A[i];
		C[A[i]-1]--;
	}
 
	delete[] C; 
	return 0;
}