Mega Code Archive

 

Categories / Java / Collections Data Structure

 

Quick Sort Implementation with median-of-three partitioning and cutoff for small arrays

public class Main {   public static void main(String args[]) {   }   public static void quicksort(Comparable[] a) {     quicksort(a, 0, a.length - 1);   }   static void quicksort(Comparable[] a, int low, int high) {     int CUTOFF = 10;     if (low + CUTOFF > high)       insertionSort(a, low, high);     else {       int middle = (low + high) / 2;       if (a[middle].compareTo(a[low]) < 0)         swapReferences(a, low, middle);       if (a[high].compareTo(a[low]) < 0)         swapReferences(a, low, high);       if (a[high].compareTo(a[middle]) < 0)         swapReferences(a, middle, high);       swapReferences(a, middle, high - 1);       Comparable pivot = a[high - 1];       int i, j;       for (i = low, j = high - 1;;) {         while (a[++i].compareTo(pivot) < 0)           ;         while (pivot.compareTo(a[--j]) < 0)           ;         if (i >= j)           break;         swapReferences(a, i, j);       }       swapReferences(a, i, high - 1);       quicksort(a, low, i - 1);        quicksort(a, i + 1, high);     }   }   public static final void swapReferences(Object[] a, int index1, int index2) {     Object tmp = a[index1];     a[index1] = a[index2];     a[index2] = tmp;   }   private static void insertionSort(Comparable[] a, int low, int high) {     for (int p = low + 1; p <= high; p++) {       Comparable tmp = a[p];       int j;       for (j = p; j > low && tmp.compareTo(a[j - 1]) < 0; j--)         a[j] = a[j - 1];       a[j] = tmp;     }   } }