#include <algorithm>
#include <vector>
using namespace std;

void Insertion(vector<int> &vInput, int nN);
void Sink(vector<int> &vInput, const int nN);
void Swap(int &nX, int &nY);
void Selection(vector<int> &vInput, const int nN);
int  Max(const vector<int> &Input, const int nN);
void QuickSort(vector<int> &vInput, const int nN);
void QuickSort(vector<int> &Input, const int nStart, const int nEnd);
int  Sorted();															//used to generate a sorted data set from which other sets are derived
void InOrder();															//used to generate a sorted data set of ARRAY_SIZE items
void Reverse();															//used to generate a reverse order data set of ARRAY_SIZE items
void Constant();														//used to generate ARRAY_SIZE number of 10's;
void AlmostSorted();													//first 90% in order, last 10% reversed
void AlmostRandom();													//first 10% in order, last 90% reversed
void AloneSelection(vector<int> &Input, const int nN);

const vector<int> ARRAY_SIZE[100];

const int nArray_Numbers = 100;



int nStart = 0;




vector<int> vArrayInsertion[nArray_Numbers];
vector<int> vArraySink[nArray_Numbers];
vector<int> vArraySelection[nArray_Numbers];
vector<int> vArrayQuickSort[nArray_Numbers];



void main(void)
{

	//AlmostRandom();
	//AlmostSorted();
	//InOrder();
	Reverse();
	//Constant();

	copy(vArrayInsertion, vArrayInsertion + nArray_Numbers, vArraySink);
	copy(vArrayInsertion, vArrayInsertion + nArray_Numbers, vArraySelection);
	copy(vArrayInsertion, vArrayInsertion + nArray_Numbers, vArrayQuickSort);
 	//copy(vArrayInsertion.begin(), vArrayInsertion.end(), vArraySink);


	//The problems are right here in this code

	Insertion(&vArrayInsertion, nArray_Numbers);
	Sink(&vArraySink, nArray_Numbers);
	AloneSelection(&vArraySelection, nArray_Numbers);
	QuickSort(&vArrayQuickSort, nArray_Numbers);

}//End of Main


int Sorted()
{
	nStart += 1;
	return nStart;
} //End Sorted()

void InOrder()
{

	generate(vArrayInsertion, vArrayInsertion + nArray_Numbers, Sorted);

} //End InOrder()


void Reverse()
{
	generate(vArrayInsertion, vArrayInsertion + nArray_Numbers, Sorted);
	reverse(vArrayInsertion, vArrayInsertion + nArray_Numbers);

} //End Reverse()


void Constant()
{
	fill(vArrayInsertion, vArrayInsertion + nArray_Numbers, 10);

} //End Constant()


void AlmostSorted()
{
	int nTenPercent = nArray_Numbers / 10;
	generate(vArrayInsertion, vArrayInsertion + nArray_Numbers, Sorted);
	reverse(vArrayInsertion + nTenPercent, vArrayInsertion + nArray_Numbers);

	reverse(vArrayInsertion, vArrayInsertion + nArray_Numbers);
}

void AlmostRandom()
{
	int nTenPercent = nArray_Numbers / 10;
	generate(vArrayInsertion, vArrayInsertion + nArray_Numbers, Sorted);
	reverse(vArrayInsertion + nTenPercent, vArrayInsertion + nArray_Numbers);

}




int  Max (const vector<int> & vInput, const int nN)
{
	int 	nL = 0;					// Subscript of the largest value in A

	for (int nM = 1; nM < nN; nM++)
		if (vInput[nM] > vInput [nL])  
			nL = nM;

	return nL;
}




void 	Swap (int& nX, int& nY)
{
	int     nTemp	= nX;
	nX		    	= nY;
	nY			    = nTemp;

	return;
}



void  Selection (vector<int> &vInput, const int nN)
{
	if (nN <= 1) 
		return;

	int nM	= Max (vInput, nN);  	    // Find the largest

	if (vInput[nM] != vInput[nN-1])         // If largest is not already last
		Swap (vInput[nM], vInput[nN-1]);	//      Swap largest with last

	Selection (vInput, nN-1);  		    // Perform selection on remaining items using recursion
	return;
}




void Insertion (vector <int>  &vInput, int nN )
{
	int	nTmp;
	int	nP, nJ;

    for (nP = 1; nP < nN; nP++)
    {
        nTmp	= vInput[nP];

        for (nJ = nP; nJ > 0 && nTmp < vInput[nJ - 1]; nJ--)
           vInput[nJ]	= vInput[nJ - 1];

        vInput[nJ]	= nTmp;
    }  // end  for
}	// end  Insertion



void  QuickSort (vector<int> &vInput, const int nN)
{
	QuickSort (vInput, 0, nN-1);
	return;
}



void  QuickSort (vector<int> &vInput, const int nStart, const int nEnd)
{
	int	    nLeft	= nStart,
			nRight	= nEnd;

	if (nLeft >= nRight)                      // If set is empty or one item, quit
			return;

	while (nLeft < nRight)					    // Partition into "Right" and "Left" sets
	{
		while ((vInput[nLeft] <= vInput[nRight]) && (nLeft < nRight))	// If in order,
			nRight --;											//       move from Right

		if (nLeft < nRight)									// If more than 1, exchange
			Swap (vInput[nLeft], vInput[nRight]);

		while ((vInput[nLeft] <= vInput[nRight]) && (nLeft < nRight))	// If in order,
			nLeft++;											//       move from left

		if (nLeft < nRight)			                        // If more than 1, exchange
			Swap (vInput[nLeft], vInput[nRight]);
	} // while (nLeft < nRight)			    // Partition into "Right" and "Left" sets
    
	QuickSort (vInput, nStart, nLeft - 1); 	    // Recursively sort "Left" partition
	QuickSort (vInput, nRight + 1, nEnd);		    // Recursively sort "Right" partition
	return;
}



void  Sink (vector<int> &vInput, const int nN)
{
	bool 	bSorted	    = false;					// Assume A not yet sorted

	int	    nPass		= 0;
	int	    nM;

	while (!bSorted && (nPass < nN))				// Sort til done or enough passes
	{
		nPass++;
		bSorted		= true;							// Assume sorted til proved wrong

		for (nM = 0; nM < (nN - nPass); nM++)
			if (vInput[nM] > vInput[nM + 1])					// If out of order then
			{
				Swap (vInput[nM], vInput[nM + 1]);			//      exchange
				bSorted = false;				// set not Sorted indicator
			}	// end if

	}	// end while
 	return;
}	// end Sink