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}