001// Exercise 2.1.9 (Solution published at http://algs4.cs.princeton.edu/) 002package algs21; 003import stdlib.*; 004import java.awt.Font; 005/* *********************************************************************** 006 * Compilation: javac TraceShell.java 007 * Execution: java TraceShell input 008 * 009 * Inserstion sort the sequence of strings specified on the command-line 010 * and show the detailed trace. 011 * 012 * % java TraceShell SORTEXAMPLE 013 * 014 *************************************************************************/ 015 016public class XTraceShell { 017 private static int line = 0; 018 019 public static void sort(String[] a) { 020 int N = a.length; 021 022 // 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ... 023 int h = 1; 024 while (h < N/3) h = 3*h + 1; 025 026 while (h >= 1) { 027 // h-sort the array 028 for (int i = h; i < N; i++) { 029 int j; 030 for (j = i; j >= h && less(a[j], a[j-h]); j -= h) { 031 exch(a, j, j-h); 032 } 033 draw(a, h, i, j); 034 line++; 035 } 036 h /= 3; 037 footer(a); 038 line++; 039 } 040 } 041 042 043 044 // exchange a[i] and a[j] 045 private static void exch(String[] a, int i, int j) { 046 String swap = a[i]; 047 a[i] = a[j]; 048 a[j] = swap; 049 } 050 051 // is v < w ? 052 private static boolean less(String v, String w) { 053 return (v.compareTo(w) < 0); 054 } 055 056 // 057 private static void draw(String[] a, int h, int ith, int jth) { 058 StdDraw.setPenColor(StdDraw.BLACK); 059 StdDraw.text(-3.75, line, h + ""); 060 StdDraw.text(-2.50, line, ith + ""); 061 StdDraw.text(-1.25, line, jth + ""); 062 for (int i = 0; i < a.length; i++) { 063 if (i == jth) StdDraw.setPenColor(StdDraw.BOOK_RED); 064 else if (i > ith) StdDraw.setPenColor(StdDraw.LIGHT_GRAY); 065 else if (i < jth) StdDraw.setPenColor(StdDraw.LIGHT_GRAY); 066 else if ((i % h) == (jth % h)) StdDraw.setPenColor(StdDraw.BLACK); 067 else StdDraw.setPenColor(StdDraw.LIGHT_GRAY); 068 StdDraw.text(i, line, a[i]); 069 } 070 } 071 072 // display header 073 private static void header(String[] a) { 074 int N = a.length; 075 076 StdDraw.setPenColor(StdDraw.BLACK); 077 StdDraw.text(N/2, -3, "a[ ]"); 078 for (int i = 0; i < N; i++) 079 StdDraw.text(i, -2, i + ""); 080 StdDraw.text(-3.75, -2, "h"); 081 StdDraw.text(-2.50, -2, "i"); 082 StdDraw.text(-1.25, -2, "j"); 083 StdDraw.setPenColor(StdDraw.BOOK_RED); 084 StdDraw.line(-4, -1.65, N-.5, -1.65); 085 StdDraw.setPenColor(StdDraw.BLACK); 086 for (int i = 0; i < a.length; i++) 087 StdDraw.text(i, -1, a[i]); 088 } 089 090 // display footer 091 private static void footer(String[] a) { 092 int N = a.length; 093 StdDraw.setPenColor(StdDraw.BLACK); 094 for (int i = 0; i < N; i++) 095 StdDraw.text(i, line, a[i]); 096 } 097 098 099 100 // test client 101 public static void main(String[] args) { 102 args = new String[] { "SORTEXAMPLE" }; 103 104 String s = args[0]; 105 int N = s.length(); 106 String[] a = ArrayGenerator.fromString (s); 107 108 // number of rows needed 109 int rows = 0; 110 int h = 1; 111 while (h < N/3) { 112 rows += (N - h + 1); 113 h = 3*h + 1; 114 } 115 rows += (N - h + 1); 116 117 // set canvas size 118 StdDraw.setCanvasSize(30*(N+3), 30*(rows+3)); 119 StdDraw.setXscale(-4, N+1); 120 // StdDraw.setYscale(N+1, -4); 121 StdDraw.setYscale(rows, -4); 122 StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13)); 123 124 // draw the header 125 header(a); 126 127 // sort the array 128 sort(a); 129 } 130 131}