/ Published in: Java
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.)
Expand |
Embed | Plain Text
import java.io.IOException; import java.text.SimpleDateFormat; import java.util.Date; import java.util.Random; /** * */ /** * @author Roger * */ public class MyQuickSort { /** * @param args */ "twain3.txt", "twain.txt", "eliot.txt", "tolstoy.txt" }; //String[] files = { "lincoln2.txt", "lincoln.txt", "twain2.txt"}; MyQuickSort sort = new MyQuickSort(); SimpleDateFormat format = for (int x = 0; x < files.length; x++) { sortTest = sort.quickSort(testCase, 0, testCase.length-1); // Make it suck... for (int i = sortTest.length - 1, j = 0; i >= 0; i--, j++) { reverseTest[j] = sortTest[i]; } suckySortTest = sort.quickSort(testCase, 0, testCase.length-1); } //for (int i = 0; i < sortTest.length; i++) { // System.out.println(sortTest[i]); //} } 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 */ 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; } 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; } list[i] = list[j]; list[j] = swap; } private int randomizeInRange(int low, int high) { assert (low < high); int retval = 0; // get the range value long range = (long)high - (long)low + 1; long fraction = (long)(range * rand.nextDouble()); retval = (int)(fraction + low); return retval; } }
You need to login to post a comment.
