#include <iostream>
#include <cmath>
using namespace std;
 
int maxIndex(int *array, int size);
void selectionSort(int *arrayIn, int sizeIn);
 
int search (int *array, int size, int thing);

int main()
{
        // create array and initialize with values
        int size ;
        cout << "How many integers do you want to enter? ";
        cin >> size;
 
        int* array = new int[size];
 
        cout << "Enter a list of " << size << " integers: " <<endl;
        for (int i = 0; i < size; i++)
               cin >> array[i];
 
        // something mysterious with the array
        selectionSort(array, size);
 
		// check for a particular value
		int thingToSearchFor = 83;
		int indexOfInterestingElement = search(array, size, thingToSearchFor);
		if (indexOfInterestingElement == size)
		{
			cout << "Not found!" << endl;
		}
		else {
			cout << "thing was found at index " << indexOfInterestingElement << endl;
		}

        // display the array
        for (int j = 0; j < size; j++)
               cout << array[j] << ' ';
        cout << endl;
 
        return 0;
}

// Returns first index of 'thing' in the array, or 'size' if not found
int search (int *array, int size, int thing) {
	for (int i=0; i<size; i++) 
	{
		if (thing == array[i])
		{
			return i;
		}

	}
	return size;
}

// Returns the index of the maximum element in the array 
int maxIndexTry1(int *array, int size)
{
	int maxIndex = 0;
	int maxValue = array[0];

	for (int i=0; i < size; i++)
	{
		if (array[i] > maxValue) 
		{
			maxIndex = i;
			maxValue = array[i];
		}
	}
    return maxIndex;
}

int maxIndex(int *array, int size)
{
	int maxIndex = 0;

	for (int i=1; i < size; i++)
	{
		if (array[i] > array[maxIndex]) 
		{
			maxIndex = i;
		}
	}
    return maxIndex;
}

bool isBefore (int thing1, int thing2)
{
	return abs(thing2) < abs(thing1);
}

int maxIndexCrazy(int *array, int size)
{
	int maxIndex = 0;

	for (int i=1; i < size; i++)
	{
		if (isBefore(array[maxIndex],array[i]) )
		{
			maxIndex = i;
		}
	}
    return maxIndex;
}


void swap (int &thing1, int &thing2) 
{
	int temp = thing1;
    thing1 = thing2;
    thing2 = temp;
}

void selectionSort(int *arrayIn, int sizeIn)
{
  for(int size = sizeIn; size > 1; size--)
  {
    int k = maxIndexCrazy(arrayIn,size);
	swap(arrayIn[k], arrayIn[size-1]);
  }
}


void selectionSortTakeTwo(int *arrayIn, int sizeIn)
{
  for(int size = sizeIn; size > 1; size--)
  {
    int k = maxIndex(arrayIn,size);
	swap(arrayIn[k], arrayIn[size-1]);
  }
}

void selectionSortTakeOne(int *arrayIn, int sizeIn)
{
  for(int size = sizeIn; size > 1; size--)
  {
    int k = maxIndex(arrayIn,size);
    int temp = arrayIn[size-1];
    arrayIn[size-1] = arrayIn[k];
    arrayIn[k] = temp;
  }
}