In this task, you are to program a hybrid sorting method, which initially works in the same way like QuickSort, but changes to InsertionSort within QuickSort as soon as the number of items that can be inserted in a substep should be smaller than k.
(a) The items you should sort are cards in a generalized card game: Each card has a color, Hearts, Diamonds, Clubs or Spades, and a value that can be any integer.
This data structure is predefined in lab/Card.java. For this class, implement the function
compareTo, which compares the current instance with another instance The comparison is first made by value and if identical, by colour ( Diamonds
compareTo should return -1
if this is truly smaller than other, 1 if this is truly larger than other and 0 if both are equal.
(b) Now implement the HybridSort.sort method in the lab/HybridSort.java file, which contains a list of cards that should be sorted in ascending order. Use the class frame/SortArray.java for the array accesses.
We use this class to count the read and write accesses to the array – Never try to bypass using this class! For the pivot element in QuickSort always use the first element in the array.
(c) The HybridOptimizer class should now calculate the optimal parameter k for given input data. To do this, implement the function optimize. The sum of the read and write operations should be minimized (You can query these values in the SortArray class).
You can also assume that there is only a (global and local) minimum – start at k = 0 and search for the first local minimum.
(d) A deterministic choice of the pivot element (such as the choice of the first, last, or middle element) can always cause QuickSort to generate a quadratic run-time input . For example, our choice of the first element (in b) leads to long
Running times.
Therefore, implement the lab/HybridSortRandomPivot.java class derived from HybridSort, which randomly selects the pivot element.
In order to produce as little duplicate code as possible, you should
write lab/HybridSort.java so that the selection of the pivot element is swapped out into a separate function, which you can then overwrite in HybridSortRandomPivot.
The zip file where the tasks should be implemented is attached as well as the frames and classes.