Sorting Fundamentals
All of the sorting algorithms are built upon two fundamental operations:
1) Comparing items to determine whether they are our of order
2) Moving items into sorted position
The advantages and disadvantages of each sorting algorithm are based on how many times these fundamental operations need to be performed and how expensive these operations are in performance terms.
Comparators
It is important to support different orderings without having to write a whole new algorithm.
A comparator is responsible for imposing a specific ordering on objects.
Separation of concerns Design Principle
Separate the concern of how to compare two individual objects (the comparator) from the concern of how to efficiently sort a large list of objects (the algorithm)
The Comparator Interface
public interface Comparator
{
public int compare(Object left, Object right);
}
The compare method throws a
ClassCastException if the type of either of the object prevents them from being compared.
The Comparable Interface
Many built-in java objects implement this interface.
public interface Comparable
{
public int compareTo(Object other);
}
The Comparator compares two objects with each other, whereas a Comparable object compares another object with itself.
Natural Comparator
A natural comparator is a comparator that supports a natural ordering of objects.
Eg. A comes before B, B comes before C and so on.
It is designed to compare two objects that implement the Comparable interface.
Java has the concept of Comparable - an interface that can be implemented by any class you are using to provide a natural sort order.
Example
public final class NaturalComparator implements Comparator
{
public static final NaturalComparator INSTANCE = new NaturalComparator();
private NaturalComparator() { ... }
public int compare(Object left, Object right)
{
assert left != null : "left cannot be null";
return ((Comparable) left).compareTo(right));
}
}
Because the NaturalComparator has no state, you only need one instance of it.
Make sure the class is marked as final to prevent it from being extended erroneously.
public void testLessThan() {
assertTrue(NaturalComparator.INSTANCE.compare(“A”, “B”) < 0);
}
public void testGreaterThan() {
assertTrue(NaturalComparator.INSTANCE.compare(“B”, “A”) > 0);
}
public void testEqualTo() {
assertTrue(NaturalComparator.INSTANCE.compare(“A”, “A”) == 0);
}
Reverse Comparator
public final class ReverseComparator implements Comparator
{
public static final NaturalComparator INSTANCE = new NaturalComparator();
private NaturalComparator() { ... }
public int compare(Object left, Object right)
{
assert left != null : "left cannot be null";
return ((Comparable) right).compareTo(left));
}
}
A better approach is to create a generic comparator that wraps (or “decorates”) another comparator and reverse the result.
public class ReverseComparator implements Comparator {
private final Comparator _comparator;
public ReverseComparator(Comparator comparator) {
assert comparator != null : “comparator can’t be null”;
_comparator = comparator;
}
public int compare(Object left, Object right) {
//Delegate to _comparator
return _comparator.compare(right, left);
}
}
Testing Reverse Comparator
public void testLessThanBecomesGreaterThan()
{
ReverseComparator comparator =
new ReverseComparator(NaturalComparator.INSTANCE);
assertTrue(comparator.compare(“A”, “B”) > 0);
}
public void testGreaterThanBecomesLessThan() {
ReverseComparator comparator =
new ReverseComparator(NaturalComparator.INSTANCE);
assertTrue(comparator.compare(“B”, “A”) < 0);
}
public void testEqualsRemainsUnchanged() {
ReverseComparator comparator =
new ReverseComparator(NaturalComparator.INSTANCE);
assertTrue(comparator.compare(“A”, “A”) == 0);
}
Bubble Sort
With each pass resulting in one item being moved into its final sorted position.
It is a stable algorithm (i.e. the algorithm maintains the relative order of items with a common sort key)
Number of comparisons is independent of the state of the input data (i.e. arrangement of the input)
public interface ListSorter
{
public List sort(List list);
}
public class BubblesortListSorter implements ListSorter
{
private final Comparator _comparator;
public BubblesortListSorter(Comparator comparator) {
assert comparator != null : "comparator cannot be null";
_comparator = comparator;
}
public List sort(List list) {
assert list != null : "list cannot be null";
int size = list.size();
for (int pass = 1; pass < size; ++pass) {
for (int left = 0; left < (size - pass); ++left) {
int right = left + 1;
if (_comparator.compare(list.get(left), list.get(right)) > 0) {
swap(list, left, right);
}
}
}
return list;
}
private void swap(List list, int left, int right) {
Object temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
}
}
Test Case
public abstract class AbstractListSorterTestCase extends TestCase {
private List _unsortedList;
private List _sortedList;
protected void setUp() throws Exception {
_unsortedList = new LinkedList();
_unsortedList.add("test");
_unsortedList.add("driven");
_unsortedList.add("development");
_unsortedList.add("is");
_unsortedList.add("one");
_unsortedList.add("small");
_unsortedList.add("step");
_unsortedList.add("for");
_unsortedList.add("a");
_unsortedList.add("programmer");
_unsortedList.add("but");
_unsortedList.add("it's");
_unsortedList.add("one");
_unsortedList.add("giant");
_unsortedList.add("leap");
_unsortedList.add("for");
_unsortedList.add("programming");
_sortedList = new LinkedList();
_sortedList.add("a");
_sortedList.add("but");
_sortedList.add("development");
_sortedList.add("driven");
_sortedList.add("for");
_sortedList.add("for");
_sortedList.add("giant");
_sortedList.add("is");
_sortedList.add("it's");
_sortedList.add("leap");
_sortedList.add("one");
_sortedList.add("one");
_sortedList.add("programmer");
_sortedList.add("programming");
_sortedList.add("small");
_sortedList.add("step");
_sortedList.add("test");
}
protected void tearDown() throws Exception {
_sortedList = null;
_unsortedList = null;
}
protected abstract ListSorter createListSorter(Comparator comparator);
public void testListSorterCanSortSampleList()
{
ListSorter sorter = createListSorter(NaturalComparator.INSTANCE);
List result = sorter.sort(_unsortedList);
assertEquals(result.size(), _sortedList.size());
Iterator actual = result.iterator();
actual.first();
Iterator expected = _sortedList.iterator();
expected.first();
while (!expected.isDone()) {
assertEquals(expected.current(), actual.current());
expected.next();
actual.next();
}
}
}
public class BubblesortListSorterTest extends AbstractListSorterTest {
protected ListSorter createListSorter(Comparator comparator) {
return new BubblesortListSorter(comparator);
}
}
Selection Sort
Each element is moved directly to its final sorted position rather than taking small steps toward its final position.
It could be made a stable algorithm.
Number of comparisons is independent of the state of the input data (i.e. arrangement of the input)
public class SelectionSortListSorter implements ListSorter {
private final Comparator _comparator;
public SelectionSortListSorter(Comparator comparator) {
assert comparator != null : "comparator cannot be null";
_comparator = comparator;
}
public List sort(List list) {
assert list != null : "list cannot be null";
int size = list.size();
for (int slot = 0; slot < size - 1; ++slot) {
int smallest = slot;
for (int check = slot + 1; check < size; ++check) {
if (_comparator.compare(list.get(check), list.get(smallest)) < 0) {
smallest = check;
}
}
swap(list, smallest, slot);
}
return list;
}
private void swap(List list, int left, int right) {
if (left == right) {
return;
}
Object temp = list.get(left);
list.set(left, list.get(right));
list.set(right, temp);
}
}
Test Case
public class SelectionSortListSorterTest extends AbstractListSorterTestCase {
protected ListSorter createListSorter(Comparator comparator) {
return new SelectionSortListSorter(comparator);
}
}
Insertion Sort
An insertion sort works by dividing the data into two groups: already sorted items and unsorted items.
One by one, an item is taken from the unsorted group and inserted at the appropriate position in the growing group of sorted items
This algorithm does not sort the objects in place by rearranging the order of the list it is given; rather, this algorithm creates a new, empty list and inserts each item from the original list into the result list in sorted order.
It is a stable algorithm (i.e. the algorithm maintains the relative order of items with a common sort key)
Number of comparisons is highly sensitive to the state of the input data.
At worst, it requires as many comparisons are the other algorithms.
At best, it requires fewer comparisons than the number of items in the input data.
public class InsertionSortListSorter implements ListSorter {
private final Comparator _comparator;
public InsertionSortListSorter(Comparator comparator) {
assert comparator != null : "comparator cannot be null";
_comparator = comparator;
}
public List sort(List list) {
assert list != null : "list cannot be null";
final List result = new LinkedList();
sort(list, result);
return result;
}
void sort(List list, final List result) {
assert list != null : "list can't be null";
assert result != null : "result can't be null";
Iterator it = list.iterator();
for (it.first(); !it.isDone(); it.next()) {
int slot = result.size();
while (slot > 0) {
if (_comparator.compare(it.current(), result.get(slot - 1)) >= 0) {
break;
}
--slot;
}
result.insert(slot, it.current());
}
}
}
Test Case
public class InsertionSortListSorterTest extends AbstractListSorterTestCase {
protected ListSorter createListSorter(Comparator comparator) {
return new InsertionSortListSorter(comparator);
}
}
