/// Find median of 5 numbers
/// Result:
/// Function  Algorithm       Swap(min, max): average Comparision(min, max): average
/// Algo1     Stl nth_element Swap (0, 3): 1.566      Comp (11, 23): 14.5832
/// Algo2     Heap            Swap (0, 5): 2.9146     Comp (4, 8): 6.7076
/// Algo33    Merge           Swap (0, 0): 0          Comp (6, 6): 6
/// Algo4     Insertion       Swap (0, 0): 0          Comp (5, 7): 6.2573
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cassert>
#include <vector>
using namespace std;

class Int {
public:
	Int(int i) : i(i) {}
	operator int() { return i; }
	friend ostream &operator<<(ostream &stream, const Int &i);
	friend bool operator< (const Int &i1, const Int &i2);
	static void Reset() { nSwap = nCom = 0; }
	void swap(Int &i2)
	{
		++Int::nSwap;
		const int temp = i;
		i = i2.i;
		i2.i = temp;
	}

	static int nSwap, nCom;
private:
	int i;
};

ostream &operator<<(ostream &stream, const Int &i)
{
	stream << i.i;;
	return stream;
}

bool operator< (const Int &i1, const Int &i2)
{
	++Int::nCom;
	return i1.i < i2.i;
}

namespace std {
template <>
void swap<Int>(Int &i1, Int &i2)
{
	i1.swap(i2);
}
}

Int &min(Int &i1, Int &i2)
{
	return (i1 < i2) ? i1 : i2;
}

#define INDEX i_##__LINE__
#define rep(n) for(int INDEX = 0; INDEX < n; ++INDEX)
int Int::nCom, Int::nSwap;

// -----------------------------------------------------------
// Swap (0, 3): 1.566
// Comp (11, 23): 14.5832
int Algo1(Int *a) {
	nth_element(a, a+2, a + 5);
	return a[2];
}

// -----------------------------------------------------------
// Swap (0, 5): 2.9146
// Comp (4, 8): 6.7076
void BalanceHeap2(Int *a) {
	if(a[1] < a[2]) {
		if(a[1] < a[0]) swap(a[0], a[1]);
	} else {
		if(a[2] < a[0]) swap(a[0], a[2]);
	}
}
void InsertInHeap2(Int *a, Int &num) {
	if(a[0] < num) {
		swap(num, a[0]);	// Actually a[0] = num; swapped for calculation management
		BalanceHeap2(a);
	}
}
int Algo2(Int *a) {
	BalanceHeap2(a);
	InsertInHeap2(a, a[3]);
	InsertInHeap2(a, a[4]);
	return a[0];
}

// -----------------------------------------------------------
int min3(Int &a, Int &b, Int &c) {
	if(a < b) {
		if(a < c) return a;
		else return c;
	} else {
		if(b < c) return b;
		else return c;
	}
}

int mid3(Int &a, Int &b, Int &c) {
	if(a < b) {
		if(a < c) {
			if(b < c) return c;
			else return b;
		} else return a;
	} else {
		if(a < c) return a;
		else {
			if(b < c) return b;
			else return c;
		}
	}
}

//Swap (0, 0): 0
//Comp (6, 6): 6
int Algo33(Int *a) {
return	a[1] < a[0] ?	a[3] < a[2] ?	a[1] < a[3] ?	a[0] < a[4] ?	a[0] < a[3] ? min(a[4],a[3]) : min(a[2],a[0])
		: a[4] < a[3] ? min(a[0],a[3])
		: min(a[2],a[4])
		: a[2] < a[4] ? a[1] < a[2] ? min(a[0],a[2])
		: min(a[4],a[1])
		: a[1] < a[4] ? min(a[0],a[4])
		: min(a[2],a[1])
		: a[1] < a[2] ? a[0] < a[4] ? a[0] < a[2] ? min(a[4],a[2])
		: min(a[3],a[0])
		: a[4] < a[2] ? min(a[0],a[2])
		: min(a[3],a[4])
		: a[3] < a[4] ? a[1] < a[3] ? min(a[0],a[3])
		: min(a[4],a[1])
		: a[1] < a[4] ? min(a[0],a[4])
		: min(a[3],a[1])
		: a[3] < a[2] ? a[0] < a[3] ? a[1] < a[4] ? a[1] < a[3] ? min(a[4],a[3])
		: min(a[2],a[1])
		: a[4] < a[3] ? min(a[1],a[3])
		: min(a[2],a[4])
		: a[2] < a[4] ? a[0] < a[2] ? min(a[1],a[2])
		: min(a[4],a[0])
		: a[0] < a[4] ? min(a[1],a[4])
		: min(a[2],a[0])
		: a[0] < a[2] ? a[1] < a[4] ? a[1] < a[2] ? min(a[4],a[2])
		: min(a[3],a[1])
		: a[4] < a[2] ? min(a[1],a[2])
		: min(a[3],a[4])
		: a[3] < a[4] ? a[0] < a[3] ? min(a[1],a[3])
		: min(a[4],a[0])
		: a[0] < a[4] ? min(a[1],a[4]) : min(a[3],a[0]);
}

// -----------------------------------------------------------
// Insertion sort
// Swap (0, 0): 0
// Comp (5, 7): 6.2658

int step4(Int &a, Int &b, Int &c, Int &d, Int &e) { // a < b < c < d
	if(e < b) {
		return b;
	} else {
		if(e < c) return e;
		else return c;
	}
}

int step3(Int &a, Int &b, Int &c, Int &d, Int &e) { // a < b < c
	if(d < b)  {
		if(d < a) return step4(d, a, b, c, e);
		else return step4(a, d, b, c, e);
	} else {
		if(d < c) return step4(a, b, d, c, e);
		else return step4(a, b, c, d, e);
	}
}

int step2(Int &a, Int &b, Int &c, Int &d, Int &e) { // a < b
	if(b < c)  { // a < b < c
		return step3(a, b, c, d, e);
	} else {
		if(a < c) return step3(a, c, b, d, e);
		else return step3(c, a, b, d, e);
	}
}

int step1(Int &a, Int &b, Int &c, Int &d, Int &e) {
	if(a < b) return step2(a, b, c, d, e);
	else  return step2(b, a, c, d, e);
}

int Algo4(Int *a) {	// I used only < or >, but refer them also as <= and >=
	return step1(a[0], a[1], a[2], a[3], a[4]);
}
// -----------------------------------------------------------
int main ()
{
	int minc = 100, mins = 100;
	int maxc = 0, maxs = 0;
	int totc = 0, tots = 0;
	srand ( (unsigned int)time(NULL) );
	const int repCount = 10000;	//1000000;	// may take up to 50 sec

	rep(repCount) {
		Int::Reset();
		const int num5Array[] = { rand(), rand(), rand(), rand(), rand() };
		//random_shuffle(num5Array, num5Array + 5);
		//rep(5) cout << num5Array[INDEX] << '\t'; cout << endl;

		vector<int> arr(num5Array, num5Array + 5);
		nth_element( arr.begin(), arr.begin()+2, arr.end() );
		const int expected = arr[2];

		vector<Int> Arr(num5Array, num5Array + 5);
		const int median = Algo33(&Arr[0]);
		assert(median == expected);
		minc = min(minc, Int::nCom); mins = min(mins, Int::nSwap);
		maxc = max(maxc, Int::nCom); maxs = max(maxs, Int::nSwap);
		totc += Int::nCom; tots += Int::nSwap;
	}
	cout << "Swap (" << mins << ',' << ' ' << maxs << "): " << tots * 1.0 / repCount << endl;
	cout << "Comp (" << minc << ',' << ' ' << maxc << "): " << totc * 1.0 / repCount << endl;
	return 0;
}

Swap (0, 0): 0
Comp (6, 6): 6