package labs.course15_16.lab2;

/* This program can be used to sort n elements with
 * the best algorithm. It is the QUICKSORT */
public class QuicksortCentralElement
	{
	static int []v;

	public static void main (String arg [] ){
	  int n= Integer.parseInt (arg[0]);  //size of the problem
	  v = new int [n];

	  Vector.sorted(v);
	  System.out.println("VECTOR TO BE SORTED:");
	  Vector.write(v);
	  quicksort(v);
	  System.out.println("SORTED VECTOR:");
	  Vector.write(v);

	  Vector.inverselySorted (v);
	  System.out.println("VECTOR TO BE SORTED:");
	  Vector.write(v);
	  quicksort(v);
	  System.out.println("SORTED VECTOR:");
	  Vector.write(v);

	  Vector.random(v, 1000000);
	  System.out.println("VECTOR TO BE SORTED:");
	  Vector.write(v);
	  quicksort(v);
	  System.out.println("SORTED VECTOR:");
	  Vector.write(v);

	}



	private static void quickSort(int elements[], int left, int right){
		int i = left;
		int j = right-1;
		int pivot;

		if (left < right){
			int center = (left+right)/2;
			if((right-left) >=3){
				pivot = elements[center];
				Util.interchange(elements, center, right);
				do{
					while (elements[i] <= pivot && i <right) i++; //first element > pivot
					while (elements[j] >=pivot && j>left) j--; //first elements < pivot
					if (i<j) Util.interchange(elements, i, j);
				} while (i < j);
				//set position of the pivot
				Util.interchange(elements, i, right);
				quickSort(elements, left, i-1);
				quickSort(elements, i+1, right);
			}
		}
	}

	public static void quicksort(int[] elements) {
		quickSort(elements, 0, elements.length-1);
	}
}