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