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}