Algoritmi di ordinamento

[Darèios89]

Vorrei chiedervi una mano sugli algoritmi di ordinamento, e sulla complessità, il primo è il SelectionSort:

public class SelectionSort
{
	public static void main(String []args)
	{
		int [] a={1,5,6,4,9,0};
		SSort(a);
		for(int i=0; i<a.length; i++)
		System.out.print(a[i]+" ");
		
	}
	
	public static void swap(int [] a, int i, int j)
	{
		int tmp=a[i];
		a[i]=a[j];
		a[j]=tmp;
	}
	
	public static void SSort(int [] a)
	{
		int min;
		for(int i=0; i<a.length-1; i++)
		{
			min=i;
			
			for(int j=i+1; j<a.length; j++)
			{
				if(a[j]<a[min])
					min=j;
			}
			
			swap(a,min,i);
		}
	}
}

La complessità secondo la notazione O-grande dovrebbe essere sempre n^2 nel caso migliore e peggiore. Perchè? Forse perchè il ciclo esterno esegue n operazioni, e anche quello interno?

Poi per quanto riguarda MergeSort e QuickSort, ho dei problemi perchè il codice non mi funziona, ci sono errori di tipo indexoutofbounds, non sono mai riuscito a sistemarlo, potreste dirmi cosa non va?

public class MergeSort
{
	
	public static void main(String [] args)
	{
		int [] a={3,6,5,7,9,8,0,5};
		MSort(a,0,a.length);
		
	}
	
	
	public static void merge(int [] a, int left,int center, int right)
	{
		int [] S=new int[a.length];
		int i= left;
		int j=center+1;
		int k=0;
	
		
		while(i<center && j<right)
		{
			if(a[i]<a[j])
			{
				S[k++]=a[i];
				i=i++;
			}
			else if(a[i]>a[j])
			{
				S[k++]=a[j];
				j=j++;
			}
		}
		
		while(i<center)
		{
			S[k++]=a[i];
			i=i++;
		}
		
		while(j<right)
		{
			S[k++]=a[j];
			j=j++;
		}
		
		for(k=left; left<=right; left++)
		a[k]=S[k-left];                        //qui c'è l'errore indexoutofbounds..
	}
	
	
	public static void MSort(int [] a,int left, int right)
	{
		
		if(left>=right) return;
		else
			{
			
			int center=(left+right)/2;
				MSort(a,left,center);
				MSort(a,center+1,right);
				merge(a, left,center,right);
			
			}

		
	
	}
}

E questo il QuickSort

public class QuickSort
{
	public static void main(String [] args)
	{
		int [] a={5,4,6,7,8,0};
		QSort(a,0,a.length-1);
	}
	
	
	public static void QSort(int [] A, int i, int r)
	{
		if(i>=r) return;
		else{
			int n=partition(A,i,r);
			QSort(A,i,n);
			QSort(A,n+1,r);
			}
	}

	public static int partition(int [] A, int i, int r)
	{
		int a=i-1;
		int b=r+1;
		int p=A[r];        //errore indexoutofbounds
		
		while(true)
		{
			b--;
			
			while(A[b]>p)
				b--;
			
		     a=a+1;
			
			while(A[a]<p)
				a=a+1;
			if(a<b)
				swap(A, a, b);
			
		else return p;
		}
	}
	
	public static void swap(int [] A,int a, int b)
	{
		int tmp=A[a];
		A[a]=A[b];
		A[b]=tmp;
	}
	
	
}

Mi sapreste poi spiegare come calcolare per questi ultimi due la complessità secondo la notazione O-Grande?