#include <iostream.h>
#include "vector.h"
#include "randgen.h"
#include "ctimer.h"

RandGen rn;

// Programmer: Sriram Pemmaraju 
// Date: Monday, April 9, 2001

void swap(Vector<int> & A, int i, int j)
{
	int t = A[i];
	A[i] = A[j];
	A[j] = t;
}

void RandomPermutation(int n, Vector<int> & A)
{
	int i;

	A.SetSize(n);
	for (i = 0; i < n; i++) 
		A[i] = i;
	for (i = 0; i < n-1; i++)
		swap(A, i, rn.RandInt(i, n-1));
			
}

void AlmostSortedPermutation(int n, Vector<int> & A)
{
	int i, j;

        A.SetSize(n);
        for (i = 0; i < n; i++) 
                A[i] = i;
        for (i = 0; i < n/10; i++){
		j = rn.RandInt(0, n-2);
                swap(A, j, j+1);
	}

}

void Heapify(int n, int i, Vector<int> & A)
{
	int largest;
	int l = 2*i+1;
	int r = 2*i+2;

	if ((l < n) && (A[l] > A[i]))
		largest = l;	
	else
		largest = i;	

	if ((r < n) && (A[r] > A[largest]))
		largest = r;

	if (largest != i)
	{
		swap(A, largest, i);
		Heapify(n, largest, A);
	}
}

void BuildHeap(int n, Vector<int> & A)
{
        int i;
        for (i = n/2-1; i >= 0; i--)
                Heapify(n, i, A);
}

void HeapSort(int n, Vector<int> & A)
{
	int i;

	BuildHeap(n, A);
	for (i = n-1; i > 0; i--)
	{
		swap(A, 0, i);
		Heapify(i, 0, A);
	}
}

int SortAndSelect(int n, int k, Vector<int> & A)
{
	HeapSort(n, A);
	return A[k-1];
}


int Partition(int p, int r, int pivot, Vector<int> & A)
{
	int q = p-1;
	int j;

	for (j = p; j <= r; j++)
		if (A[j] <= pivot){
			swap(A, j, q+1);	
			q++;
		}
	return q;
}

int RandomSelect(int p, int r, int k, Vector<int> & A)
{
	int i, pivot, q, size;

	if (p == r)
		return A[p];
	else if (p < r)
	{
		pivot = A[rn.RandInt(p, r)];
		q = Partition(p, r, pivot, A);
		size = q - p + 1;	
		if (k <= size)
			return RandomSelect(p, q, k, A);
		else
			return RandomSelect(q+1, r, k-size, A);
		
	}
}	

int min(int x, int y)
{
	if (x <= y) 
		return x;
	else 
		return y;
}

void GetMediansOfFive(int p, int r, const Vector<int> & A, Vector<int> & B)
{
	int sizeOfB = B.Length();
	int size = A.Length();
	int u, i, j;
	Vector<int> T(5);

	for (i = 0; i < sizeOfB; i++)
	{
		u = min(5*i+4, size-1);
		for (j = 5*i; j <= u; j++) 
			T[j-5*i] = A[j];
		HeapSort(u-5*i+1, T);
		B[i] = T[(u-5*i+1)/2];
	}
}

int Select(int p, int r, int k,  Vector<int> & A)
{
	int size = r - p + 1;
	int i, pivot, q;

	if (size <= 10){
		Vector<int> B(size);
		for (i = 0; i < size; i ++)
			B[i] = A[p+i];

		return SortAndSelect(size, k, B);
	}
	else {
		int sizeOfB = size/5;
		if (size % 5 != 0)
			sizeOfB++;

		Vector<int> B(sizeOfB);

		GetMediansOfFive(p, r, A, B);
		pivot = Select(0, sizeOfB-1, sizeOfB/2, B);
		q = Partition(p, r, pivot, A);
                size = q - p + 1;
                if (k <= size)
                        return RandomSelect(p, q, k, A);
                else
                        return RandomSelect(q+1, r, k-size, A);
		
		
	}
		
}

int main()
{
	Vector<int> A;
	int i, m, n;
	CTimer t;
	int lb = 1000; 
	int ub = 20000; 
	int inc = 1000;
	int times = 50;

	cout << "Random Permutation: SortAndSelect" << endl;
	for (n = lb; n <= ub; n = n + inc)
	{
		for (i = 0; i < times; i++)
		{
			RandomPermutation(n, A);
			t.Start();
			m = SortAndSelect(n, n/2, A);
			t.Stop();
		}
		cout << t.CumulativeTime()/times <<", ";
		t.Reset();
	}
	cout << endl;

	t.Reset();
	cout << "Random Permutation: RandomSelect" << endl;
        for (n = lb; n <= ub; n = n + inc)
        {
                for (i = 0; i < times; i++)
                {
                        RandomPermutation(n, A);
                        t.Start();
                        m = RandomSelect(0, n-1, n/2, A);
                        t.Stop();
                }
                cout << t.CumulativeTime()/times <<", ";
		t.Reset();
        }
        cout << endl;

	t.Reset();
        cout << "Random Permutation: Select" << endl;
        for (n = lb; n <= ub; n = n + inc)
        {
                for (i = 0; i < times; i++)
                {
                        RandomPermutation(n, A);
                        t.Start();
                        m = Select(0, n-1, n/2, A);
                        t.Stop();
                }
                cout << t.CumulativeTime()/times <<", ";
		t.Reset();
        }
        cout << endl;

	t.Reset();
	cout << "Almost Sorted Permutation: SortAndSelect" << endl;
        for (n = lb; n <= ub; n = n + inc)
        {
                for (i = 0; i < times; i++)
                {
                        AlmostSortedPermutation(n, A);
                        t.Start();
                        m = SortAndSelect(n, n/2, A);
                        t.Stop();
                }
                cout << t.CumulativeTime()/times <<", ";
		t.Reset();
        }
        cout << endl;

        t.Reset();
        cout << "Almost Sorted Permutation: RandomSelect" << endl;
        for (n = lb; n <= ub; n = n + inc)
        {
                for (i = 0; i < times; i++)
                {
                        AlmostSortedPermutation(n, A);
                        t.Start();
                        m = RandomSelect(0, n-1, n/2, A);
                        t.Stop();
                }
                cout << t.CumulativeTime()/times <<", ";
		t.Reset();
        }
        cout << endl;

        t.Reset();
        cout << "Almost Sorted Permutation: Select" << endl;
        for (n = lb; n <= ub; n = n + inc)
        {
                for (i = 0; i < times; i++)
                {
                        AlmostSortedPermutation(n, A);
                        t.Start();
                        m = Select(0, n-1, n/2, A);
                        t.Stop();
                }
                cout << t.CumulativeTime()/times <<", ";
		t.Reset();
        }
	cout << endl;

	return 0;
}