Saturday, December 01, 2007

Selection Sort With Comparator

Selection sort works by finding the smallest unsorted element in the collection and swapping it with an item in the position that's to be filled next. Because swaps don't happen all the time, this algorithm is a little but more efficient than bubblesort (about 60% better).
The algorithm is a ϑ(n2) complexity computation, efficient enough for small problem sizes. Here's a Java implementation of the algorithm that uses a comparator to specify more complex ordering criteria.

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 SelectionsortListSorter implements ListSorter {
private final Comparator comparator;

public SelectionsortListSorter(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 slot = 1; 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;
}
}
Utilities.swap(list, smallest, slot);
}
return list;
}
}