package util;
/**
* Suprise. A QuickSort... probably already existed, but I had the code, and
* wanted to add sorting an array of objects based on an array of values...
*/
public class QuickSort {
	private QuickSort(float[] array) {
		float []a ;
		a = qsort(array,0,array.length-1);
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]) ;
		}

	}


	public static void sort(int[] A) {
		float[] temp = new float[A.length] ;
		for (int i = 0; i < A.length; i++) {
			temp[i] = (float)A[i];
		}
		qsort(temp,0,temp.length-1) ;
		for (int i = 0; i < A.length; i++) {
			A[i] = (int)temp[i];
		}
	}
	public static void sort(float[] A) {
		qsort(A,0,A.length-1) ;
	}

	

	public static void sort(Object[] objs, float[]A) {
		// Sort an array of objects on A
		qsort(A,0,A.length-1,objs) ;
	}



	private static float[] qsort(float[] A, int p, int r, Object[] objs) {
		int q ;
		if (p<r) {
			q=partition(A,p,r,objs);
			qsort(A,p,q,objs) ;
			qsort(A,q+1,r,objs) ;
		}
		return A;
	}



	private static float[] qsort(float[] A, int p, int r) {
		int q ;
		if (p<r) {
			q=partition(A,p,r,null);
			qsort(A,p,q) ;
			qsort(A,q+1,r) ;
		}
		return A;
	}



	private static int partition(float[] A, int p, int r, Object[] objs) {
		float temp = 0f;
		Object objectTemp = null;
		float x = A[p];
		int i = p-1;
		int j = r+1;

		while (true) {
			do { j--; } while (A[j]>x);
			
			do { i++; } while (A[i]<x);

			if (i < j) {
				temp = A[i] ;
				A[i] = A[j] ;
				A[j] = temp;
				if (objs != null) {
					objectTemp = objs[i]; 
					objs[i] = objs[j];
					objs[j] = objectTemp;
				}
			} else {
				return j;
			}
				
		}
	}
	
	
	
	public static void main(String []args) {
		float []a = {2f,1f};
		new QuickSort(a) ;
	}
}	