001// Exercise 2.3.2 (Solution published at http://algs4.cs.princeton.edu/)
002package algs23;
003import stdlib.*;
004import java.awt.Font;
005/* ***********************************************************************
006 *  Compilation:  javac TraceQuick.java
007 *  Execution:    java  TraceQuick input
008 *
009 *  Quicksort the sequence of strings specified as the command-line
010 *  arguments and show the detailed trace.
011 *
012 *  % java TraceQuick QUICKSORTEXAMPLE
013 *
014 *************************************************************************/
015
016public class XTraceQuick {
017        private static int line = 0;
018
019
020        public static void sort(String[] a) {
021                sort(a, 0, a.length - 1);
022        }
023
024        private static void sort(String[] a, int lo, int hi) {
025                if (hi < lo) return;
026                if (hi == lo) {
027                        draw(a, lo);
028                        line++;
029                        return;
030                }
031                int j = partition(a, lo, hi);
032                draw(a, lo, j, hi);
033                line++;
034                sort(a, lo, j-1);
035                sort(a, j+1, hi);
036        }
037
038        private static int partition(String[] a, int lo, int hi) {
039                int i = lo;
040                int j = hi + 1;
041                String v = a[lo];
042                while (true) {
043
044                        // find item on lo to swap
045                        while (less(a[++i], v))
046                                if (i == hi) break;
047
048                        // find item on hi to swap
049                        while (less(v, a[--j]))
050                                if (j == lo) break;      // redundant since a[lo] acts as sentinel
051
052                        // check if pointers cross
053                        if (i >= j) break;
054
055                        exch(a, i, j);
056                }
057
058                // put v = a[j] into position
059                exch(a, lo, j);
060
061                // with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
062                return j;
063        }
064
065
066        // exchange a[i] and a[j]
067        private static void exch(String[] a, int i, int j) {
068                String swap = a[i];
069                a[i] = a[j];
070                a[j] = swap;
071        }
072
073        // is v < w ?
074        private static boolean less(String v, String w) {
075                return (v.compareTo(w) < 0);
076        }
077
078        // draw the contents of the array, with a[lo] in red
079        private static void draw(String[] a, int lo) {
080                StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
081                StdDraw.text(-3.75, line, lo + "");
082                StdDraw.text(-1.25, line, lo + "");
083                for (int i = 0; i < a.length; i++) {
084                        if (i == lo)  StdDraw.setPenColor(StdDraw.BOOK_RED);
085                        else          StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
086                        StdDraw.text(i, line, a[i]);
087                }
088        }
089
090
091        // draw the contents of the array, with a[lo] to a[hi] in black
092        private static void draw(String[] a, int lo, int j, int hi) {
093                StdDraw.setPenColor(StdDraw.BLACK);
094                StdDraw.text(-3.75, line, lo + "");
095                StdDraw.text(-1.25, line, hi + "");
096                StdDraw.setPenColor(StdDraw.BOOK_RED);
097                StdDraw.text(-2.50, line, j  + "");
098                for (int i = 0; i < a.length; i++) {
099                        if (i == j)                  StdDraw.setPenColor(StdDraw.BOOK_RED);
100                        else if (i >= lo && i <= hi) StdDraw.setPenColor(StdDraw.BLACK);
101                        else                         StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
102                        StdDraw.text(i, line, a[i]);
103                }
104        }
105
106        // display header
107        private static void header(String[] a) {
108                int N = a.length;
109                StdDraw.setPenColor(StdDraw.BLACK);
110                StdDraw.text(N/2.0, -4, "a[ ]");
111                for (int i = 0; i < N; i++)
112                        StdDraw.text(i, -3, i + "");
113                StdDraw.text(-3.75, -3, "lo");
114                StdDraw.text(-2.50, -3, "j");
115                StdDraw.text(-1.25, -3, "hi");
116                StdDraw.setPenColor(StdDraw.BOOK_RED);
117                StdDraw.line(-4, -2.65, N-.5, -2.65);
118                StdDraw.setPenColor(StdDraw.BLACK);
119                for (int i = 0; i < a.length; i++)
120                        StdDraw.text(i, -2, a[i]);
121                StdRandom.shuffle(a);
122                for (int i = 0; i < a.length; i++)
123                        StdDraw.text(i, -1, a[i]);
124        }
125
126        // display footer
127        private static void footer(String[] a) {
128                int N = a.length;
129                StdDraw.setPenColor(StdDraw.BLACK);
130                for (int i = 0; i < N; i++)
131                        StdDraw.text(i, line, a[i]);
132        }
133
134
135        // test client
136        public static void main(String[] args) {
137                args = new String[] { "SORTEXAMPLE" };
138
139                // parse command-line argument as an array of 1-character strings
140                String s = args[0];
141                int N = s.length();
142                String[] a = new String[N];
143                for (int i = 0; i < N; i++)
144                        a[i] = s.substring(i, i+1);
145
146                // set canvas size
147                StdDraw.setCanvasSize(30*(N+3), 30*(N+3));
148                StdDraw.setXscale(-4, N+1);
149                StdDraw.setYscale(N+1, -4);
150                StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13));
151
152                // display the header
153                header(a);
154
155                // sort the array and display trace
156                sort(a);
157
158                // display the footer
159                footer(a);
160        }
161
162}