Posted By

rtperson on 05/08/12


Tagged

java algorithm quicksort


Versions (?)

Quicksort in Java, with Enforced Suckitude


 / 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.)

  1. import java.io.IOException;
  2. import java.text.SimpleDateFormat;
  3. import java.util.Date;
  4. import java.util.Random;
  5.  
  6. /**
  7.  *
  8.  */
  9.  
  10. /**
  11.  * @author Roger
  12.  *
  13.  */
  14. public class MyQuickSort {
  15.  
  16. /**
  17.   * @param args
  18.   */
  19. public static void main(String[] args) throws IOException {
  20. String[] files = { "lincoln2.txt", "lincoln.txt", "twain2.txt",
  21. "twain3.txt", "twain.txt", "eliot.txt", "tolstoy.txt" };
  22. //String[] files = { "lincoln2.txt", "lincoln.txt", "twain2.txt"};
  23.  
  24. MyQuickSort sort = new MyQuickSort();
  25.  
  26. new SimpleDateFormat("EEE MMM dd HH:mm:ss-SSS zzz yyyy");
  27. String[] sortTest = null;
  28. String[] suckySortTest = null;
  29.  
  30. System.out.println("---------TEST QUICK SORT ------------");
  31. for (int x = 0; x < files.length; x++) {
  32. String[] testCase = MergeTest.readFile(files[x]);
  33.  
  34. long start = System.currentTimeMillis();
  35. Date now = new Date(start);
  36. System.out.println("File: " + files[x]);
  37. System.out.println("Total words: " + testCase.length);
  38. System.out.println("begin test: " + format.format(now));
  39.  
  40. sortTest = sort.quickSort(testCase, 0, testCase.length-1);
  41.  
  42. long end = System.currentTimeMillis();
  43. now = new Date(end);
  44. System.out.println("end test: " + format.format(now));
  45. System.out.println("total time: " + (end - start));
  46. System.out.println("--------------------------\n\n");
  47.  
  48. // Make it suck...
  49. String[] reverseTest = new String[sortTest.length];
  50. for (int i = sortTest.length - 1, j = 0; i >= 0; i--, j++) {
  51. reverseTest[j] = sortTest[i];
  52. }
  53.  
  54. start = System.currentTimeMillis();
  55. now = new Date(start);
  56. System.out.println("-------SUCKY VERSION----------");
  57. System.out.println("File: " + files[x]);
  58. System.out.println("Total words: " + testCase.length);
  59. System.out.println("begin test: " + format.format(now));
  60.  
  61. suckySortTest = sort.quickSort(testCase, 0, testCase.length-1);
  62.  
  63. end = System.currentTimeMillis();
  64. now = new Date(end);
  65. System.out.println("end test: " + format.format(now));
  66. System.out.println("total time: " + (end - start));
  67. System.out.println("--------------------------\n\n");
  68. }
  69.  
  70.  
  71. //for (int i = 0; i < sortTest.length; i++) {
  72. // System.out.println(sortTest[i]);
  73. //}
  74.  
  75. }
  76.  
  77. private String[] quickSort(String[] list, int low, int high) {
  78. if (high <= low) return list;
  79. //int pivot = partition(list, low, high);
  80. int pivot = nonSuckyPartition(list, low, high);
  81. quickSort(list, low, pivot-1);
  82. quickSort(list, pivot+1, high);
  83.  
  84. return list;
  85. }
  86.  
  87. /**
  88.   * Sucky version of partition -- it uses the first element as the partition.
  89.   * @param list
  90.   * @param low
  91.   * @param high
  92.   * @return
  93.   */
  94. private int partition(String[] list, int low, int high) {
  95. int i = low - 1;
  96. int j = high;
  97. while (i < high) {
  98. while (list[++i].compareTo(list[high]) < 0) ; // do nothing
  99. while (list[high].compareTo(list[--j]) < 0) {
  100. if (j == low) break;
  101. }
  102. if (i >= j) break;
  103. swap(list, i, j);
  104. }
  105. swap(list, i, high);
  106. return i;
  107. }
  108.  
  109. private int nonSuckyPartition(String[] list, int low, int high) {
  110. int i = low - 1;
  111. int j = high;
  112. int partition = randomizeInRange(low, high);
  113. while (i < high) {
  114. while (list[++i].compareTo(list[partition]) < 0) ; // do nothing
  115. while (list[partition].compareTo(list[--j]) < 0) {
  116. if (j == low) break;
  117. }
  118. if (i >= j) break;
  119. swap(list, i, j);
  120. }
  121. swap(list, i, high);
  122. return i;
  123. }
  124.  
  125. private void swap(String[] list, int i, int j) {
  126. String swap = list[i];
  127. list[i] = list[j];
  128. list[j] = swap;
  129. }
  130.  
  131. private int randomizeInRange(int low, int high) {
  132. assert (low < high);
  133. int retval = 0;
  134. Random rand = new Random();
  135. // get the range value
  136. long range = (long)high - (long)low + 1;
  137. long fraction = (long)(range * rand.nextDouble());
  138. retval = (int)(fraction + low);
  139.  
  140. return retval;
  141. }
  142.  
  143.  
  144. }

Report this snippet  

You need to login to post a comment.