001// Exercise 2.3.1 (Solution published at http://algs4.cs.princeton.edu/) 002package algs23; 003import stdlib.*; 004import java.awt.Font; 005/* *********************************************************************** 006 * Compilation: javac TracePartition.java 007 * Execution: java TracePartition string 008 * 009 * Partitions the array of characters specified as the command-line 010 * argument and shows the detailed trace. 011 * 012 * % java TracePartition KRATELEPUIMQCXOS 013 * 014 * % java TracePartition AAAAAAAAAAAAAAAA 015 * 016 *************************************************************************/ 017 018public class XTracePartition { 019 private static int line = 0; 020 021 private static int partition(String[] a) { 022 int lo = 0, hi = a.length - 1; 023 int i = lo; 024 int j = hi + 1; 025 String v = a[lo]; 026 while (true) { 027 028 // find item on lo to swap 029 int iold = i + 1; 030 while (less(a[++i], v)) 031 if (i == hi) break; 032 033 // find item on hi to swap 034 int jold = j - 1; 035 while (less(v, a[--j])) 036 if (j == lo) break; // redundant since a[lo] acts as sentinel 037 038 // check if pointers cross 039 if (i >= j) break; 040 041 draw(a, iold, i, jold, j); 042 line++; 043 044 exch(a, i, j); 045 draw(a, i, j); 046 line++; 047 } 048 049 // put v = a[j] into position 050 exch(a, lo, j); 051 draw(a, lo, j); 052 line++; 053 054 // with a[lo .. j-1] <= a[j] <= a[j+1 .. hi] 055 return j; 056 } 057 058 059 // exchange a[i] and a[j] 060 private static void exch(String[] a, int i, int j) { 061 String swap = a[i]; 062 a[i] = a[j]; 063 a[j] = swap; 064 } 065 066 // is v < w ? 067 private static boolean less(String v, String w) { 068 return (v.compareTo(w) < 0); 069 } 070 071 private static void draw(String[] a, int iold, int ith, int jold, int jth) { 072 StdDraw.setPenColor(StdDraw.BLACK); 073 StdDraw.text(-2.50, line, ith + ""); 074 StdDraw.text(-1.25, line, jth + ""); 075 for (int i = 0; i < a.length; i++) { 076 if (i >= iold && i <= ith) StdDraw.setPenColor(StdDraw.BLACK); 077 else if (i <= jold && i >= jth) StdDraw.setPenColor(StdDraw.BLACK); 078 else StdDraw.setPenColor(StdDraw.LIGHT_GRAY); 079 StdDraw.text(i, line, a[i]); 080 } 081 } 082 083 private static void draw(String[] a, int ith, int jth) { 084 StdDraw.setPenColor(StdDraw.BOOK_RED); 085 StdDraw.text(-2.50, line, ith + ""); 086 StdDraw.text(-1.25, line, jth + ""); 087 for (int i = 0; i < a.length; i++) { 088 if (i == ith || i == jth) StdDraw.setPenColor(StdDraw.BOOK_RED); 089 else StdDraw.setPenColor(StdDraw.LIGHT_GRAY); 090 StdDraw.text(i, line, a[i]); 091 } 092 } 093 094 // display header 095 private static void header(String[] a) { 096 int N = a.length; 097 StdDraw.setPenColor(StdDraw.BLACK); 098 StdDraw.text(N/2.0, -3, "a[ ]"); 099 for (int i = 0; i < N; i++) 100 StdDraw.text(i, -2, i + ""); 101 StdDraw.text(-2.50, -2, "i"); 102 StdDraw.text(-1.25, -2, "j"); 103 StdDraw.setPenColor(StdDraw.BOOK_RED); 104 StdDraw.line(-3, -1.65, N-.5, -1.65); 105 StdDraw.setPenColor(StdDraw.BLACK); 106 for (int i = 0; i < a.length; i++) 107 StdDraw.text(i, -1, a[i]); 108 } 109 110 // display footer 111 private static void footer(String[] a, int j) { 112 int N = a.length; 113 StdDraw.setPenColor(StdDraw.BOOK_RED); 114 StdDraw.text(-1.25, line, j + ""); 115 for (int i = 0; i < N; i++) { 116 if (i == j) StdDraw.setPenColor(StdDraw.BOOK_RED); 117 else StdDraw.setPenColor(StdDraw.BLACK); 118 StdDraw.text(i, line, a[i]); 119 } 120 } 121 122 123 // test client 124 public static void main(String[] args) { 125 args = new String[] { "SORTEXAMPLE" }; 126 127 // parse command-line argument as an array of 1-character strings 128 String s = args[0]; 129 int N = s.length(); 130 String[] a = new String[N]; 131 for (int i = 0; i < N; i++) 132 a[i] = s.substring(i, i+1); 133 134 // set canvas size 135 StdDraw.setCanvasSize(30*(N+3), 30*(N+3)); 136 StdDraw.setXscale(-4, N+1); 137 StdDraw.setYscale(N+1, -4); 138 StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13)); 139 140 // display the header 141 header(a); 142 143 // sort the array and display trace 144 int j = partition(a); 145 146 // display the footer 147 footer(a, j); 148 } 149 150}