The goal of this exercise is to practice and understand sorting algorithms, and through them, gain a deeper understanding of how to analyze the performance of algorithms.
Sorting algorithms are a good candidate for this purpose, since they are well understood, relatively simple, but allow an exploration of computational complexity.
The goal of a sorting algorithm is to put a collection of given objects in an order, as desired by the user. For some objects (e.g. Integer, Double), an order is relatively easy to understand and explain, and relatively intuitive. A collection of numerical values can be placed in ascending order (i.e. lower values first, in increasing order) or descending order (i.e. highest value first, and then decreasing).
But what about arbitrary objects? How can we compare two objects of any other type? In order to decide on the "order" between two objects of arbitrary class, we use an object called 'Comparator'. This allows a developer to decide what is a meaningful method of providing an order for the classes they are developing.
Write a class called OptimizedBubbleSort with the following method:
public <T> int sort(T[] array, Comparator<T> comparator, boolean optimized)
The method should sort the input array based on a given Comparator.
The method should return the number of times the method Comparator#compare is called.
If optimized is true, then instead of a naive bubble sort, you should run a better version.
For example, one fact that can be exploited is that, if the last swap is done at position i, then
all elements after i are necessarily sorted.
So, in the next iteration, you do not need to check elements after i.
Write a class called OptimizedBubbleSortTest in which you test your implementation.
You need at least one test with the following input array ["c", "b", "a", "d", "e", "f"].
On such array, you need to verify that your optimized bubble sort version should do less than
half the comparisons than a non-optimized version.
Note: be careful to do not call sorting twice on the same array, but rather create a new one.
Add enough unit tests until your reach 100% statement coverage.
Consider the class org.pg4200.ex03.GameUser.
Write a class called GameUserComparator that does
implement Comparator<GameUser>.
A GameUser is "larger" if it has more points.
If points are the same, should consider alphabetic sorting
based on the user id.
Add a new test in OptimizedBubbleSortTest in which you
sort an array of GameUser using GameUserComparator.
Develop a class called SortCheckerImp and that implements
the interface org.pg4200.ex03.SortChecker.
Develop a test class called SortCheckerImpTest that
does extend org.pg4200.ex03.SortCheckerTestTemplate,
in which you test your SortCheckerImp implementation.
If it is correct, all tests should pass.
Study the source code of BubbleSort and InsertionSort.
Once you think you fully understand them, write their implementation
on paper (e.g., using a pen), without looking at the source code.
Once done, compare what you wrote with the actual implementations.
Solutions to this exercise can be found in the solutions
module, under the org.pg4200.sol03 package.