Your assignment should consist of a single file called hw2.cpp that
contains:

your name

 * a class timer (given here):

	class Timer{

		int start;
	public:
		Timer(){start=clock();}
		void reset(){start=clock();}
		double elapsed(){return (clock()-start)/CLOCKS_PER_SEC;}
	};

 * the function fill_array

 * the three functions topm_1, topm_2, and topm_3

 * the function max_element

 * the function quicksort

 * the function quickselect

 * a function main whose output looks something like this:

   ______________________________________________________________
   Which algorithm (1,2,3 or 0=exit): 1
   Enter the value of n: 10000
   Enter the value of m: 10
   Generating random array of length 10000.
   The top 10 numbers in the array are
   32767  32764  32764  32760  32758  32750  32748  32746  32745  32739
   Time to compute: approx. 0.01 sec
   Which algorithm (1,2,3 or 0=exit): 3
   Enter the value of n: 10000
   Enter the value of m: 10
   Generating random array of length 10000.
   The top 10 numbers in the array are
   32767 32766 32758 32758 32757 32751 32736 32735 32732 32732
   Time to compute: approx. 0 sec
   Which algorithm (1,2,3 or 0=exit): 0
   Thank you.
   ______________________________________________________________

Before the main function executes an algorithm, it should generate an
array of the appropriate size (implemented as a vector), and fill that
array with random positive integers using the function fill_array.

The problem addressed in this programming assignment is to output,
in decreasing order, the largest m elements in an unsorted input array
of n elements.  The entries of the input array are assumed to be
positive integers.

For example, if the input array is [27, 52, 66, 55, 13, 10, 100, 7]
and m=4, then the algorithm should output
100, 66, 55, 52

Note: If the array contains duplicate values, then the output
list may contain duplicates.  For example, if the input array is
[10 2 7 4 10 5 7 9] and m=5, then the output should be 10 10 9 7 7

Call this problem the "top m problem".

1) Consider the following algorithm for solving the top m problem.

***********************************************************
  Repeat m times on the array:

     Find the maximum element in the array (if there's more
        than one, find just one.)
     Output it
     Replace it in the array with the number 0.

***********************************************************

Write a function max_element(const vector <int> &A) that returns
the index of the maximum element of the array.

Then write a function
topm_1(const vector <int> & A, int m) which
implements the above algorithm for solving the top m problem.


2) A second algorithm for solving the top m problem is as follows.

************************************************************

    Sort the array using quicksort.
    Use the median of three method for partitioning.

    Output the elements in positions n-1 through n-m in the
    sorted array.

************************************************************



Write a function topm_2(const vector <int> & A, int m) which
implements this second algorithm.
The function topm_2 should call a quicksort function,
which you should also write.  Your quicksort function
should use median-of-three partitioning, but shouldn't
use a cutoff (that is, it shouldn't call insertion sort
on small arrays).  So, it should be similar to the quicksort code
on p. 347, but without the cutoff.

Warning: The quicksort code on p. 347 does partitioning in lines
22 through 33.  This partitioning does not work
properly for arrays of size 2 (The code was written assuming
that CUTOFF was at least 4, so that quicksort is
only used on arrays of length at least 3.)
You should handle arrays of size 2 as a special case.

3) A third algorithm for solving the top m problem uses
the quickselect algorithm discussed in Section 9.7 of the
textbook.

************************************************************

     Use quickselect to find the mth largest element in
     the array (that is, the element of
     rank n-m+1).  When quickselect finishes, the
     largest m elements in the array will be in positions
     n-m through n-1 of the copied array, but they
     may not be in sorted order.

     Sort the largest m elements using quicksort, and output
     them in descending order.

************************************************************

Write a function topm_3(const vector <int> & A, int m) that
implements this third algorithm, and calls quicksort and
a quickselect function.  You should also write quickselect.
Your quickselect can be essentially like the version
in the textbook on p. 350, but do not use a cutoff
(that is, do not do insertion sort for small arrays).
Again, as with quicksort, you should handle arrays
of length 2 as a special case.


4) Write a function fill_array(A)
that takes as input a vector A, and fills the
entries of the vector with random positive integers.
You will probably want to use the function rand(),
which requires you to include the header file <cstdlib>.
The expression (1 + rand()) will produce
a random positive integer between 1 and
RAND_MAX + 1.  RAND_MAX is a constant
whose value is defined in cstdlib (in one
recent version of stdlib, RAND_MAX is 32767).

5) Using an STL multiset container, design a sorting algorithm for any datatype (which can be stored in the set).  Remember a multiset stores things in sorted order.

Your function should have the following interface:
void mySort1(vector<int>& v);  //not int, but ANY data type.