package algorithms.sort;

public class QuickSorter<Template extends Comparable<Template>> extends Sorter<Template>
{
	public void sort(Template[] array,int from,int length)
	{
		quickSort(array,from,from+length-1);
	}

	private void quickSort(Template[] array,int from,int to)
	{
		if(to-from<=1)
			return;
		int mid = (from+to)/2;
		int partition = partition(array,from,to,mid);
		quickSort(array,from,partition-1);
		quickSort(array,partition+1,to);
	}
	
	private int partition(Template[] array,int from,int to,int mid)
	{
		Template temp = array[mid];
		array[mid] = array[to];
		
		while(from!=to)
		{
			while(from<to && array[from].compareTo(temp)<=0)
				from++;
			if(from<to)
				array[to--] = array[from];
			while(from<to && array[to].compareTo(temp)>=0)
				to--;
			if(from<to)
				array[from++] = array[to];			
		}
		array[from] = temp;
		return from;
	}
	
	/*
	public static void main(String[] args)
	{		
		Integer[] a = {2,3,4,2,4,7,6,33,77,2,55,6};
		
		System.out.println("a[8]:"+a[8].intValue());
		
		QuickSorter<Integer> qs = new QuickSorter<Integer>();
		System.out.println("a[9]:"+a[9].intValue());
		qs.sort(a);
		System.out.println("a[10]:"+a[10].intValue());
		qs.print(a);
		System.out.println("length:"+a.length);		
	}
	*/
}