import java.io.IOException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.Random;

/**
 * 
 */

/**
 * @author Roger
 *
 */
public class MyQuickSort {
    
    /**
     * @param args
     */
    public static void main(String[] args) throws IOException {
        String[] files = { "lincoln2.txt", "lincoln.txt", "twain2.txt", 
                "twain3.txt", "twain.txt", "eliot.txt", "tolstoy.txt" };
        //String[] files = { "lincoln2.txt", "lincoln.txt", "twain2.txt"};
        
        MyQuickSort sort = new MyQuickSort();
        
        SimpleDateFormat format =
            new SimpleDateFormat("EEE MMM dd HH:mm:ss-SSS zzz yyyy");
        String[] sortTest = null;
        String[] suckySortTest = null;
        
        System.out.println("---------TEST QUICK SORT ------------");
        for (int x = 0; x < files.length; x++) {
            String[] testCase = MergeTest.readFile(files[x]);
            
            long start = System.currentTimeMillis();
            Date now = new Date(start);
            System.out.println("File: " + files[x]);
            System.out.println("Total words: " + testCase.length);
            System.out.println("begin test: " + format.format(now));    
            
            sortTest = sort.quickSort(testCase, 0, testCase.length-1);

            long end = System.currentTimeMillis();
            now = new Date(end);
            System.out.println("end test: " + format.format(now));
            System.out.println("total time: " + (end - start));
            System.out.println("--------------------------\n\n");
            
            // Make it suck...
            String[] reverseTest = new String[sortTest.length];
            for (int i = sortTest.length - 1, j = 0; i >= 0; i--, j++) {
                reverseTest[j] = sortTest[i];
            }
            
            start = System.currentTimeMillis();
            now = new Date(start);
            System.out.println("-------SUCKY VERSION----------");
            System.out.println("File: " + files[x]);
            System.out.println("Total words: " + testCase.length);
            System.out.println("begin test: " + format.format(now));
          
            suckySortTest = sort.quickSort(testCase, 0, testCase.length-1);
            
            end = System.currentTimeMillis();
            now = new Date(end);
            System.out.println("end test: " + format.format(now));
            System.out.println("total time: " + (end - start));
            System.out.println("--------------------------\n\n");
        }
              
        
        //for (int i = 0; i < sortTest.length; i++) {
        //    System.out.println(sortTest[i]);
        //}

    }
    
    private String[] quickSort(String[] list, int low, int high) {
        if (high <= low) return list;
        //int pivot =  partition(list, low, high);
        int pivot =  nonSuckyPartition(list, low, high);
        quickSort(list, low, pivot-1);
        quickSort(list, pivot+1, high);
        
        return list;
    }
    
    /**
     * Sucky version of partition -- it uses the first element as the partition.
     * @param list
     * @param low
     * @param high
     * @return
     */
    private int partition(String[] list, int low, int high) {
        int i = low - 1;
        int j = high;
        while (i < high) {
            while (list[++i].compareTo(list[high]) < 0) ; // do nothing
            while (list[high].compareTo(list[--j]) < 0) {
                if (j == low) break;
            }
            if (i >= j) break;
            swap(list, i, j);
        }
        swap(list, i, high);
        return i;
    }
    
    private int nonSuckyPartition(String[] list, int low, int high) {
        int i = low - 1;
        int j = high;
        int partition = randomizeInRange(low, high);
        while (i < high) {
            while (list[++i].compareTo(list[partition]) < 0) ; // do nothing
            while (list[partition].compareTo(list[--j]) < 0) {
                if (j == low) break;
            }
            if (i >= j) break;
            swap(list, i, j);
        }
        swap(list, i, high);
        return i;
    }
    
    private void swap(String[] list, int i, int j) {
        String swap = list[i];
        list[i] = list[j];
        list[j] = swap;
    }
    
    private int randomizeInRange(int low, int high) {
        assert (low < high);
        int retval = 0;
        Random rand = new Random();
        // get the range value
        long range = (long)high - (long)low + 1;
        long fraction = (long)(range * rand.nextDouble());
        retval = (int)(fraction + low);
        
        return retval;
    }


}

It's no fun implementing QuickSort unless you can force it out of its blister-fast, O(n log n) speed and humiliate it with its worst-case, O(n^2) runtime. So that's what I set out to do.  

My naive partition simply pivots around the low item, but my randomized partition defeats the sucky inputs by choosing a random pivot. (If you're interested in checking out a QuickSort which naively partitions until it hits an attempt to get it to run in quadratic time, check out IntroSort -- which simply  fails over to Merge Sort when it exceeds its optimal recursion depth.)

Quicksort in Java, with Enforced Suckitude

java

Java