Problem 2: Polymorphism
The goal of this in-lecture exercise is to get familiar with designing extensible classes, and understand inheritance and polymorphism.
Suppose we want to provide a benchmark way for comparing a variety of sorting algorithms, based on the number of comparisons and swaps they require for sorting.
Focus solely in sorting integers. Assume that the integers to sort: (i) are stored in an array which length is defined by the only parameter that is passed to the program; (ii) are generated random and uniformelly in the interval [0,100*length of the array]. For this purpose use the java.util.Random class.
All sorting algorithms should rely on two methods:
- compare: receives two integers, representing two indexes of the array, and performs a comparison of the elements in those indexes. It returns an integer value, 0 if those values are equal, -1 if the first value is less than the second one, and 1 if the first value is greater than the second one.
- swap: receives two integers, representing two indexes of the array, and performs a swap of the elements at those indexes of the array. It returns void.
- sort: a no-arg method that returns void. This method sorts the elements in the array using compare and swap methods only. The purpose of compare and swap methods is to make them responsible to track the number of comparisons and swaps performed by each sorting algorithm.
Implement this problem in Java making the solution as extensible as possible. Test the program and check the statistics on the number of comparison and swaps performed by selection and bublle sort algorithms.
In the end answer to the following questions:
- Does the implementation is as extensible as possible?
- Does the superclass trust its extended classes?
- Where does polymorphism apply?