001package algs21;
002import stdlib.*;
003import java.awt.Font;
004/* ***********************************************************************
005 *  Compilation:  javac TraceBubble.java
006 *  Execution:    java  TraceBubblrinput
007 *
008 *  Bubble sort the sequence of strings specified on the command-line
009 *  and show the detailed trace.
010 *
011 *  % java TraceBubble SORTEXAMPLE
012 *
013 *************************************************************************/
014
015public class XTraceBubble {
016
017        // bubble sort
018        public static void sort (String[] a) {
019                int N = a.length;
020                for (int i = 0; i < N; i++) {
021                        int j;
022                        for (j = 1; j < (N - i); j++) {
023                                if (less (a[j], a[j - 1])) {
024                                        exch (a, j, j - 1);
025                                }
026                        }
027                        draw(a, i, 1, j-1);
028                }
029        }
030
031
032        // exchange a[i] and a[j]
033        private static void exch(String[] a, int i, int j) {
034                String swap = a[i];
035                a[i] = a[j];
036                a[j] = swap;
037        }
038
039        // is v < w ?
040        private static boolean less(String v, String w) {
041                return (v.compareTo(w) < 0);
042        }
043
044        //
045        private static void draw(String[] a, int row, int ith, int jth) {
046                StdDraw.setPenColor(StdDraw.BLACK);
047                StdDraw.text(-2.50, row, ith + "");
048                StdDraw.text(-1.25, row, jth + "");
049                for (int i = 0; i < a.length; i++) {
050                        if (i == jth)      StdDraw.setPenColor(StdDraw.BOOK_RED);
051                        else if (i < jth)  StdDraw.setPenColor(StdDraw.BLACK);
052                        else               StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
053                        StdDraw.text(i, row, a[i]);
054                }
055        }
056
057        // display header
058        private static void header(String[] a) {
059                int N = a.length;
060
061                StdDraw.setPenColor(StdDraw.BLACK);
062                StdDraw.text(N/2, -3, "a[ ]");
063                for (int i = 0; i < N; i++)
064                        StdDraw.text(i, -2, i + "");
065                StdDraw.text(-2.50, -2, "i");
066                StdDraw.text(-1.25, -2, "j");
067                StdDraw.setPenColor(StdDraw.BOOK_RED);
068                StdDraw.line(-3, -1.65, N-.5, -1.65);
069                StdDraw.setPenColor(StdDraw.BLACK);
070                for (int i = 0; i < a.length; i++)
071                        StdDraw.text(i, -1, a[i]);
072        }
073
074        // display footer
075        private static void footer(String[] a) {
076                int N = a.length;
077                StdDraw.setPenColor(StdDraw.BLACK);
078                for (int i = 0; i < a.length; i++)
079                        StdDraw.text(i, N, a[i]);
080        }
081
082
083
084        // test client
085        public static void main(String[] args) {
086                // parse command-line argument as an array of 1-character strings
087                //args = new String[] { "9876543210" };
088                args = new String[] { "SORTEXAMPLE" };
089
090                String s = args[0];
091                int N = s.length();
092                String[] a = ArrayGenerator.fromString (s);
093
094                // set canvas size
095                StdDraw.setCanvasSize(30*(N+3), 30*(N+3));
096                StdDraw.setXscale(-3, N+1);
097                StdDraw.setYscale(N+1, -3);
098                StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13));
099
100                // draw the header
101                header(a);
102
103                // sort the array
104                sort(a);
105
106                // draw the footer
107                footer(a);
108        }
109
110}