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