1 /*************************************************************************
2 * Compilation: javac QuickSort.java
3 * Execution: java QuickSort N
4 *
5 * Generate N random real numbers between 0 and 1 and quicksort them.
6 *
7 * On average, this quicksort algorithm runs in time proportional to
8 * N log N, independent of the input distribution. The algorithm
9 * guards against the worst-case by randomly shuffling the elements
10 * before sorting. In addition, it uses Sedgewick's partitioning
11 * method which stops on equal keys. This protects against cases
12 * that make many textbook implementations, even randomized ones,
13 * go quadratic (e.g., all keys are the same).
14 *
15 *************************************************************************/
16
17 public class QuickSort {
18 private static long comparisons = 0;
19 private static long exchanges = 0;
20
21 /***********************************************************************
22 * Quicksort code from Sedgewick 7.1, 7.2.
23 ***********************************************************************/
24 public static void quicksort(double[] a) {
25 shuffle(a); // to guard against worst-case
26 quicksort(a, 0, a.length - 1);
27 }
28
29 // quicksort a[left] to a[right]
30 public static void quicksort(double[] a, int left, int right) {
31 if (right <= left) return;
32 int i = partition(a, left, right);
33 quicksort(a, left, i-1);
34 quicksort(a, i+1, right);
35 }
36
37 // partition a[left] to a[right], assumes left < right
38 private static int partition(double[] a, int left, int right) {
39 int i = left - 1;
40 int j = right;
41 while (true) {
42 while (less(a[++i], a[right])) // find item on left to swap
43 ; // a[right] acts as sentinel
44 while (less(a[right], a[--j])) // find item on right to swap
45 if (j == left) break; // don't go out-of-bounds
46 if (i >= j) break; // check if pointers cross
47 exch(a, i, j); // swap two elements into place
48 }
49 exch(a, i, right); // swap with partition element
50 return i;
51 }
52
53 // is x < y ?
54 private static boolean less(double x, double y) {
55 comparisons++;
56 return (x < y);
57 }
58
59 // exchange a[i] and a[j]
60 private static void exch(double[] a, int i, int j) {
61 exchanges++;
62 double swap = a[i];
63 a[i] = a[j];
64 a[j] = swap;
65 }
66
67 // shuffle the array a[]
68 private static void shuffle(double[] a) {
69 int N = a.length;
70 for (int i = 0; i < N; i++) {
71 int r = i + (int) (Math.random() * (N-i)); // between i and N-1
72 exch(a, i, r);
73 }
74 }
75
76
77
78 // test client
79 public static void main(String[] args) {
80 int N = Integer.parseInt(args[0]);
81
82 // generate N random real numbers between 0 and 1
83 long start = System.currentTimeMillis();
84 double[] a = new double[N];
85 for (int i = 0; i < N; i++)
86 a[i] = Math.random();
87 long stop = System.currentTimeMillis();
88 double elapsed = (stop - start) / 1000.0;
89 System.out.println("Generating input: " + elapsed + " seconds");
90
91 // sort them
92 start = System.currentTimeMillis();
93 quicksort(a);
94 stop = System.currentTimeMillis();
95 elapsed = (stop - start) / 1000.0;
96 System.out.println("Quicksort: " + elapsed + " seconds");
97
98 // print statistics
99 System.out.println("Comparisons: " + comparisons);
100 System.out.println("Exchanges: " + exchanges);
101 }
102 }
103