001// Exercise 2.1.4 (Solution published at http://algs4.cs.princeton.edu/)
002package algs21;
003import stdlib.*;
004import java.awt.Font;
005/* ***********************************************************************
006 *  Compilation:  javac TraceInsertion.java
007 *  Execution:    java  TraceInsertion input
008 *
009 *  Insertion sort the sequence of strings specified on the command-line
010 *  and show the detailed trace.
011 *
012 *  % java TraceInsertion SORTEXAMPLE
013 *
014 *************************************************************************/
015
016public class XTraceInsertion {
017
018        // insertion sort
019        public static void sort(String[] a) {
020                int N = a.length;
021                for (int i = 0; i < N; i++) {
022                        int j;
023                        for (j = i; j > 0 && less(a[j], a[j-1]); j--) {
024                                exch(a, j, j-1);
025                        }
026                        draw(a, i, i, j);
027                }
028        }
029
030
031        // exchange a[i] and a[j]
032        private static void exch(String[] a, int i, int j) {
033                String swap = a[i];
034                a[i] = a[j];
035                a[j] = swap;
036        }
037
038        // is v < w ?
039        private static boolean less(String v, String w) {
040                return (v.compareTo(w) < 0);
041        }
042
043        //
044        private static void draw(String[] a, int row, int ith, int jth) {
045                StdDraw.setPenColor(StdDraw.BLACK);
046                StdDraw.text(-2.50, row, ith + "");
047                StdDraw.text(-1.25, row, jth + "");
048                for (int i = 0; i < a.length; i++) {
049                        if (i == jth)      StdDraw.setPenColor(StdDraw.BOOK_RED);
050                        else if (i > ith)  StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
051                        else if (i < jth)  StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
052                        else               StdDraw.setPenColor(StdDraw.BLACK);
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[] { "SORTEXAMPLE" };
088
089                String s = args[0];
090                int N = s.length();
091                String[] a = ArrayGenerator.fromString (s);
092
093                // set canvas size
094                StdDraw.setCanvasSize(30*(N+3), 30*(N+3));
095                StdDraw.setXscale(-3, N+1);
096                StdDraw.setYscale(N+1, -3);
097                StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13));
098
099                // draw the header
100                header(a);
101
102                // sort the array
103                sort(a);
104
105                // draw the footer
106                footer(a);
107        }
108
109}