The goal for this exercise is to implement the QuickSort sorting algorithm.
Based on your personal research on the QuickSort algorithm, as well as the in-class preview, you should implement the QuickSort sorting algorithm.
You should do this by adding a method named QuickSort onto your SearchingAndSorting class, which takes as it's sole parameter an array of, say, integers. This public method should then call the private, recursive method (which takes as parameters the original array to be sorted, and the starting & ending indeces of the array to be sorted), much like so:
public class SortingAndSearching
{
// Your comment here about
// 1) Running time
// 2) Required space
public void QuickSort(int[] nums)
{
QuickSort(nums, 0, nums.Length - 1);
// Note: According to the in-class slides, you should pass
// nums.Length as the 'end' parameter – it can work either way,
// but you'll need to be careful, and consistent
}
private void QuickSort( int[] nums, //this spacing is actually legal
int iStart,
int iEnd)
{
// work done here...
}
}
You should also clearly document the running time and space required, in Big "Oh" notation, in a comment just above the public version. You should also clearly explain WHY the method has the running time & space requirements, clearly, and intuitively. For the space requirements, make sure to clearly list what space is required (i.e., the temporary working array, as well as anything else), and how you get from those individual space requirements to the overall requirements for the algorithm.
What you need to do for this exercise:
1.
In the provided
starter solution, in the PCE_Starter project, you should find a class named SortingAndSearching. You should implement QuickSort, as
described above.
2.
Once you’ve done
this, all the tests in the Test_QuickSort class should pass.
3. You should include a comment, immediately above the public QuickSort method, which documents the running time, and the required space
a. This needs to be done using the Big Oh notation
b. You need to include a quick (2-3 sentence) explanation about why the running time & required space that you chose is correct.