In this lab, we are going to continue with our design of the journey planner. So we will reuse most of the earlier files. Your job in this lab is to help us print the list of all trains leaving from a station, sorted time wise and day-of-the-week wise.
Towards this end, you will have to implement Quicksort, but now operating on a list of objects of type TrainInfoPerStation (see dictionary.h for definition of this class). The only constraint we have here is that Quicksort has to be done on a list of objects, and you are not allowed to use too much extra space. So for example, copying the list into an array and sorting it is not acceptable. You must also choose a random pivot, not one that is always at the end of the list.
The constraints we have for you are: For a list with n elements, you can use additional storage space of amount n/K, for a given K, and your random pivot choice function can use only O(K) time. We’ll start with K = 4, say.
So simply traversing the list to choose a pivot won’t work, since here the choice of the random pivot will end up taking O(n) time.
You have to implement the function Quicksort invoked in function printStationInfo in planner.cpp.
You should only submit planner.cpp and quicksort.cpp for your submission (of course, as a .tgz file)
