Saturday, December 01, 2007

Bubblesort With Comparator

Bubblesort works by iterating over items in a list and swapping adjucent elements into the required order. Iteration continues until no more swaps are required.
You can make sorting more generic by using comparators. This allows a sorter to sort any collection of data using more complex criteria specified in a comparator. Here's a simple implementation:


package com.strive.research.algorithms.sorting;

import java.util.Comparator;
import com.strive.research.algorithms.lists.List;
import com.strive.research.algorithms.util.Utilities;

@SuppressWarnings("unchecked")
public class BubblesortListSorter implements ListSorter {
private final Comparator comparator;

public BubblesortListSorter(Comparator comparator) {
assert(comparator != null): "Comparator cannot be null";
this.comparator = comparator;
}

@Override
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) {
Utilities.swap(list, left, right);
}
}
}
return list;
}
}


The meat of the algorithm is public List sort(List list), which all implementors of my custom ListSorter interface must implement. This algorithm does in-place sorting, so there is no need to return the list really. Bubblesort is a ϑ(n2) complexity computation, efficient enough for small problem sizes.

No comments: