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