001// Exercise 2.2.2 (Solution published at http://algs4.cs.princeton.edu/) 002package algs24; 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 XTraceHeap { 017 private static int line = 0; 018 019 public static void sort(String[] pq) { 020 int N = pq.length; 021 for (int k = N/2; k >= 1; k--) { 022 sink(pq, k, N); 023 draw (pq, N, k); line++; 024 } 025 while (N > 1) { 026 exch(pq, 1, N--); 027 sink(pq, 1, N); 028 draw (pq, N, 1); line++; 029 } 030 } 031 032 /* ********************************************************************* 033 * Helper functions to restore the heap invariant. 034 **********************************************************************/ 035 036 private static void sink(String[] pq, int k, int N) { 037 while (2*k <= N) { 038 int j = 2*k; 039 if (j < N && less(pq, j, j+1)) j++; 040 if (!less(pq, k, j)) break; 041 exch(pq, k, j); 042 k = j; 043 } 044 } 045 046 /* ********************************************************************* 047 * Helper functions for comparisons and swaps. 048 * Indices are "off-by-one" to support 1-based indexing. 049 **********************************************************************/ 050 private static boolean less(String[] pq, int i, int j) { 051 return pq[i-1].compareTo(pq[j-1]) < 0; 052 } 053 054 private static void exch(String[] pq, int i, int j) { 055 String swap = pq[i-1]; 056 pq[i-1] = pq[j-1]; 057 pq[j-1] = 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 067 private static void draw(String[] a, int N, int k) { 068 StdDraw.setPenColor(StdDraw.BLACK); 069 StdDraw.text(-2.50, line, N + ""); 070 StdDraw.text(-1.25, line, k + ""); 071 for (int i = 0; i < a.length; i++) { 072 StdDraw.text(i, line, a[i]); 073 } 074 } 075 076 // display header 077 private static void header(String[] a) { 078 int N = a.length; 079 StdDraw.setPenColor(StdDraw.BLACK); 080 StdDraw.text(N/2, -3, "a[ ]"); 081 for (int i = 0; i < N; i++) 082 StdDraw.text(i, -2, i + ""); 083 StdDraw.text(-2.50, -2, "N"); 084 StdDraw.text(-1.25, -2, "k"); 085 StdDraw.setPenColor(StdDraw.BOOK_RED); 086 StdDraw.line(-4, -1.65, N-.5, -1.65); 087 StdDraw.setPenColor(StdDraw.BLACK); 088 for (int i = 0; i < a.length; i++) 089 StdDraw.text(i, -1, a[i]); 090 } 091 092 // display footer 093 private static void footer(String[] a) { 094 int N = a.length; 095 StdDraw.setPenColor(StdDraw.BLACK); 096 for (int i = 0; i < a.length; i++) 097 StdDraw.text(i, line, a[i]); 098 } 099 100 101 // test client 102 public static void main(String[] args) { 103 args = new String[] { "SORTEXAMPLE" }; 104 105 // parse command-line argument as an array of 1-character strings 106 String s = args[0]; 107 int N = s.length(); 108 String[] a = new String[N]; 109 for (int i = 0; i < N; i++) 110 a[i] = s.substring(i, i+1); 111 112 // set canvas size 113 StdDraw.setCanvasSize(30*(N+3), (int) (30*(1.5*N+3))); 114 StdDraw.setXscale(-4, N+1); 115 StdDraw.setYscale(1.5*N+1, -4); 116 StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13)); 117 118 // display the header 119 header(a); 120 121 // sort the array and display trace 122 sort(a); 123 124 // display the footer 125 footer(a); 126 } 127 128}