====== Algoritmi di Ordinamento ======
Autore: **//Santo Patti//**

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

==Insertion Sort==
Complessità nel caso migliore O(//n//), nel caso peggiore O(//n//²)

<code c>
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;
}
</code>

==Merge Sort==
Complessità nel caso migliore O(//n//log//n//), nel caso peggiore O(//n//log//n//)
<code c>
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);
	}
}
</code>

==Quick Sort==

Complessità nel caso migliore O(//n//log//n//), nel caso peggiore O(//n//log//n//).

<code c>
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;
}

</code>

==Counting Sort==

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

<code c>
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;
}
</code>