public class QuickSort implements Sortierer{ //jetzt auch Comparable-Array sortieren
	
	//Sortierer fuer int-Arrays
	public void sort(int[]A){
		rekursivQuickSort(A,0,A.length-1);
	}
	void rekursivQuickSort(int A[], int links, int rechts){
		if(links>=rechts)return;
		int i=links, j=rechts, p=A[(links+rechts)/2];
		do{
			while(A[i]<p)i++;
			while(A[j]>p)j--;
			if (i<=j){
				Mylib.tausche(A,i,j);
				i++; j--;
			}
		} while(i<=j);
		rekursivQuickSort(A, links, j);
		rekursivQuickSort(A, i, rechts);
			
	}
	
	//Sortierer für-Comparable-Arrays
	public void sort(Comparable A[]){
		rekursivQuickSort(A,0,A.length-1);
	}
	void rekursivQuickSort(Comparable A[], int links, int rechts){
		if(links>=rechts)return;
		int i=links, j=rechts; 
		Comparable p=A[(links+rechts)/2];
		do{
			while(A[i].compareTo(p)==-1)i++;
			while(A[j].compareTo(p)==1)j--;
			if (i<=j){
				Mylib.tausche(A,i,j);
				i++; j--;
			}
		} while(i<=j);
		rekursivQuickSort(A, links, j);
		rekursivQuickSort(A, i, rechts);
			
	}
	
	public static void main(String args[]){
		int meinArray[]= Mylib.makeRandomArray(200);
		Mylib.intArrayAusgeben("Unsortierter Array", meinArray);
		QuickSort Q=new QuickSort();
		Q.sort(meinArray);
		Mylib.intArrayAusgeben("Mit QuickSort sortierter Array", meinArray);
	}

	public String toString(){
		return "Quicksort";
	}

}