#include <iostream>

using namespace std;

double median(double arr[], int size);
double mode(double arr[], int size);

char ch;
string temp;
int k = 0;
double * input_arr = NULL;

// This assignment is worth 6 points
// +3 for successful implementation of median
// +3 for successful implementation of mode

int main()
{
	int length;

	cout << "Enter array size: ";
	cin >> length;
	cin.ignore();

	input_arr = new double[length];

	cout << "Enter numbers: ";
	do
	{
		cin >> input_arr[k];
		k++;
		ch = cin.get();
	} while(ch != '\n' && k < length);
	if(k == length && ch != '\n')
		getline(cin, temp);

	cout << "The median is " << median(input_arr, length) << endl;
	cout << "The mode is " << mode(input_arr, length) << endl;

	return 0;
}

double median(double arr[], int size)
{
	int index_smallest;	// The index where the smallest value is
	// Sort the array first
	for(int i = 0; i < size; i++)
	{
		index_smallest = i;
		for(int j = i+1; j < size; j++)
		{
			if(arr[j] < arr[index_smallest])
				index_smallest = j;
		}
		if(index_smallest != i)
		{	// Swap the values
			arr[i] += arr[index_smallest];
			arr[index_smallest] = arr[i] - arr[index_smallest];
			arr[i] -= arr[index_smallest];
		}
	}

	if(size % 2 == 1)
		return arr[size/2];
	else
		return (arr[size/2]+arr[size/2-1])/2.0;
}

// Here's a method to find the mode without needing to sort or store values.
// It's just a matter of running through every possible combination.
double mode(double arr[], int size)
{
	int counter, high_count = 1, mode;
	for(int i = 0; i < size; i++)
	{
		counter = 0;
		for(int j = 0; j < size; j++)
		{
			if(arr[i] == arr[j])
				counter++;
		}
		if(counter > high_count)
		{
			mode = arr[i];
			high_count = counter;
		}
	}
	return mode;
}