This will again be a partnered lab. For this lab, you must work with the same parter you had for lab 5. As usual, run update35 to get the initial files for this lab. Note: after running update35, you should see an 06 subdirectory of your 05 directory (i.e., you'll get a directory cs35/labs/05/06). We put lab 06 here because you'll be submitting labs 5 and 6 simultaneously, and this will enable you to submit both with one command.

This lab consists of three parts:

1. A short problem set to get experience working through merge sort and quick sort
2. Complete a templated implementation of quickSort and its helper function, partition
3. Thoroughly test your quickSort implementation.

This problem set generalizes the findMax and findMin problems you've seen previously. The median of an array of n items is the element in the middle. If n is odd, then exactly (n-1)/2 elements are smaller than the median, and (n-1)/2 elements are bigger. (If n is even, define the median so that n/2 items are bigger, and n/2-1 items are smaller).

1. Using only pseudocode, describe a divide-and-conquer algorithm findMedian(A) for finding the median element of an array. Your solution must be faster than simply sorting the array and finding the element in the middle. You may use methods defined in class (such as partition, merge, swap) without redefining them. HINT: your solution should look very similar to one of mergeSort or quickSort. Which of these two algorithms can be shortened to find the median?
2. Again, using only pseudocode, describe a divide-and-conquer algorithm findKthBiggest(A,k) for finding the kth biggest item in the array. As with the median algorithm, your solution must be fast, and you may use methods defined in class without redefining them.

Include pseudocode for both algorithms in the appropriate places in your README file.

The templated quick sort algorithm is to be defined in quickSort.h and quickSort-inl.h. We have provided the declaration for you, so no modifications are needed in quickSort.h. The algorithm is broken into four components:

• quickSort(T a[], int n, CMP compare) - the main quick sort method that is called by the user. Notice that there are two templates: T for the type of data in the array (e.g., int, float) and CMP for the comparison operator to use. This allows us to make the sorting algorithm general in terms of how it decides to sort items. There is an example in testQuickSort.
• quickSort(T a[], int start, int end, CMP compare) - the recursive version of quick sort that is only used internally to sort a sub range of the array. You must implement this method
• partition(T a[], int start, int end, CMP compare) - partitions the array a in the given subrange. You must implement a random-pivot version of partition
• swap(T a[], int i, int j) - swaps two elements in the array. This has been given to you.

To complete this work, you mainly only need to code in the locations marked with TODO. Once you are done, you can test your work using the provided testQuickSort program which sorts an array of ints for you. Specifically, implement the following:

• the recursive quickSort is fairly straight forward, follow the pseudocode from class.
• your partition function should use a random pivot rather than the right-most element. Simply pick a random index in the subrange and swap it with the right-most element. Then, you can follow the normal partition pseudocode relying on the right-most element. To pick a random number, use rand() to return a integer between 0 and RAND_MAX (a compiler defined max value for integers).

  range = end-start+1      //range of values to pick from
  index = (rand() % range) //random int from 0 to range-1
  index = index+start      //int is from start to end
  swap(a,index,end)        //move random pivot to end
  
  proceed with normal partition
  

• The second change to the pseudocode from class is the comparison method. Rather than only sorting in ascending order, we let the caller define how to sort the array. This also lets the caller define how to sort complex data (e.g., Point objects). For example, we can define how to sort ints from smallest to largest using lessInt (in randArray-inl.h):

  bool lessInt(int a, int b){
    return a < b;
  }
  

  When calling quickSort, we send this function in to the parameter compare. Our partition function while loop then looks as follows:

  while (left <= right):
    if (compare(a[left], pivotValue)):
      left++
    else if (!compare(a[right],pivotValue)):
      right--
    else:
      swap(a, left, right)
  

  If we use lessInt:
  • compare(a[left],pivotValue) is equivalent to a[left] < pivotValue
  • !compare(a[right],pivotValue) is equivalent to a[right] >= pivotValue.

As you complete your quickSort, you should test your implementation using the code provided in testQuickSort. We have provided one test sorting an array of ints. You will need to study the implementation using the files testQuickSort.cpp and helper functions in randArray.h/-inl.h. Then, add two more tests to testQuickSort:

• A test for sorting ints in descending order (largest to smallest). This will require you to implement the function greaterInt and send this as the argument for the compare function.
• A test to sort floats. You can sort in either ascending or descending order. You will need to implement lessFloat and greaterFloat to complete this test.

Once you have completed the test, note how this is an example of polymorphism. We have written a sorting method that can work on any data type as long as it has a defined method for comparing two objects. While it is beyond the scope of the assignment, you should think about how you can compare two Point objects and note that this would allow you to sort an array of Point objects. For example, we could define the following comparator that returns true if a has a smaller x value OR a smaller yvalue if the x value's are equal:

bool lessPoints(Point a, Point b){
  if(a.getX() == b.getX()){
    return a.getY() < b.getY();
  } else if(a.getX() < b.getX()){
    return true;
  } else {
    return false;
  }
}

Run handin35 to submit your quick sort implementation, test program, and solutions to the pseudocode problems.