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