001// Exercise 2.1.1 (Solution published at http://algs4.cs.princeton.edu/)
002package algs21;
003import stdlib.*;
004import java.awt.Font;
005/* ***********************************************************************
006 *  Compilation:  javac TraceSelection.java
007 *  Execution:    java  TraceSelection input
008 *
009 *  Selection sort the sequence of strings specified on the command-line
010 *  and show the detailed trace.
011 *
012 *  % java TraceSelection SORTEXAMPLE
013 *
014 *************************************************************************/
015
016public class XTraceSelection {
017
018        // selection sort
019        public static void sort(String[] a) {
020                int N = a.length;
021                for (int i = 0; i < N; i++) {
022                        int min = i;
023                        for (int j = i+1; j < N; j++) {
024                                if (less(a[j], a[min])) min = j;
025                        }
026                        draw(a, i, i, min);
027                        exch(a, i, min);
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        // exchange a[i] and a[j]
045        private static void draw(String[] a, int row, int ith, int min) {
046                StdDraw.setPenColor(StdDraw.BLACK);
047                StdDraw.text(-2.50, row, ith + "");
048                StdDraw.text(-1.25, row, min + "");
049                for (int i = 0; i < a.length; i++) {
050                        if (i == min)     StdDraw.setPenColor(StdDraw.BOOK_RED);
051                        else if (i < ith) StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
052                        else              StdDraw.setPenColor(StdDraw.BLACK);
053                        StdDraw.text(i, row, a[i] + "");
054                }
055        }
056
057
058        // display header
059        private static void header(String[] a) {
060                int N = a.length;
061
062                StdDraw.setPenColor(StdDraw.BLACK);
063                StdDraw.text(N/2, -3, "a[ ]");
064                for (int i = 0; i < N; i++)
065                        StdDraw.text(i, -2, i + "");
066                StdDraw.text(-2.50, -2, "i");
067                StdDraw.text(-1.25, -2, "min");
068                StdDraw.setPenColor(StdDraw.BOOK_RED);
069                StdDraw.line(-3, -1.65, N-.5, -1.65);
070                StdDraw.setPenColor(StdDraw.BLACK);
071                for (int i = 0; i < a.length; i++)
072                        StdDraw.text(i, -1, a[i]);
073        }
074
075        // display footer
076        private static void footer(String[] a) {
077                int N = a.length;
078                StdDraw.setPenColor(StdDraw.BLACK);
079                for (int i = 0; i < a.length; i++)
080                        StdDraw.text(i, N, a[i]);
081        }
082
083        // test client
084        public static void main(String[] args) {
085                args = new String[] { "SORTEXAMPLE" };
086
087                String s = args[0];
088                int N = s.length();
089                String[] a = ArrayGenerator.fromString (s);
090
091                // set canvas size
092                StdDraw.setCanvasSize(30*(N+3), 30*(N+3));
093                StdDraw.setXscale(-3, N+1);
094                StdDraw.setYscale(N+1, -3);
095                StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13));
096
097                // draw the header
098                header(a);
099
100                // sort the array
101                sort(a);
102
103                // draw the footer
104                footer(a);
105        }
106
107}