Monday, November 16, 2009

quicksort in java

This is an alternate version of quicksort in java, in response to Chris Wong's post On Conciseness

  
List<Comparable> sort(List<Comparable> list) {
    List<Comparable> sorted  = new ArrayList<Comparable>();
    List<Comparable> less    = new ArrayList<Comparable>();
    List<Comparable> same    = new ArrayList<Comparable>();
    List<Comparable> greater = new ArrayList<Comparable>();

    if (list.size() > 0) {
        Comparable pivot = list.get(0);

        for (Comparable x: list) {
            if      (x.compareTo(pivot) < 0)    less.add(x);
            else if (x.compareTo(pivot) > 0) greater.add(x);
            else                                same.add(x);
        }
        sorted.addAll(sort(less));
        sorted.addAll(same);
        sorted.addAll(sort(greater));
    }
    return sorted;
}
  

No comments:

Post a Comment