
package source.Utility;

//
// Utility Program for TETDM 
// Qsort.java Version 0.01
// Copyright(C) 2007 TETDM CORE MEMBER ALL RIGHTS RESERVED.
// This program is provided under the license.
//

public class Qsort
{
	public static void init_num(int num[], int n)
	{
		int i;

		for(i=0;i<n;i++)
			num[i] = i;
	}


	public static void quicksort(double a[],int num[], int n)
	{
		int i,bn=0,cn=0;
		double b[] = new double[n];
		double c[] = new double[n];
		int bnum[] = new int[n];
		int cnum[] = new int[n];

		double temp,border;
		int t;

		if(n == 0 || n == 1)
			return;

		if(n == 2)
		{
			if(a[1] > a[0])
			{
				temp = a[0];
				a[0] = a[1];
				a[1] = temp;
				t = num[0];
				num[0] = num[1];
				num[1] = t;
			}
			return;
		}

		for(i=0,border=0;i<n;i++)
			border += a[i];
		border /= n;

		for(i=0,bn=0,cn=0;i<n;i++)
			if(a[i] > border)
			{
				bnum[bn] = num[i];
				b[bn++] = a[i];
			}
			else
			{
				cnum[cn] = num[i];
				c[cn++] = a[i];
			}

		if(bn != 0 && cn != 0)
		{
			quicksort(b,bnum,bn);
			quicksort(c,cnum,cn);

			for(i=0;i<bn;i++)
			{
				a[i] = b[i];
				num[i] = bnum[i];
			}
			for(i=bn;i<bn+cn;i++)
			{
				a[i] = c[i-bn];
				num[i] = cnum[i-bn];
			}
		}
	}

	//return Nth ranked data
	public static double quickselect(double a[], int n, int rank)
	{
		int i,bn=0,cn=0;
		double b[] = new double[n];
		double c[] = new double[n];
		double border, r;

		if(n == 0)
			return 100000000;

		if(n == 1)
			return a[0];

		for(i=1;i<n;i++)
			if(a[i] - a[0] < -0.000001 || a[i] - a[0] > 0.000001)
				break;
		if(i == n)
			return a[0];

		for(i=0,border=0;i<n;i++)
			border += a[i];
		border /= (double)n;

		for(i=0,bn=0,cn=0;i<n;i++)
			if(a[i] > border)
				b[bn++] = a[i];
			else
				c[cn++] = a[i];

		if(rank <= bn)
			r = quickselect(b,bn,rank);
		else
			r = quickselect(c,cn,rank-bn);

		return r;
	}
}
