001package algs21; 002import stdlib.*; 003import java.awt.Font; 004/* *********************************************************************** 005 * Compilation: javac TraceBubble.java 006 * Execution: java TraceBubblrinput 007 * 008 * Bubble sort the sequence of strings specified on the command-line 009 * and show the detailed trace. 010 * 011 * % java TraceBubble SORTEXAMPLE 012 * 013 *************************************************************************/ 014 015public class XTraceBubble { 016 017 // bubble sort 018 public static void sort (String[] a) { 019 int N = a.length; 020 for (int i = 0; i < N; i++) { 021 int j; 022 for (j = 1; j < (N - i); j++) { 023 if (less (a[j], a[j - 1])) { 024 exch (a, j, j - 1); 025 } 026 } 027 draw(a, i, 1, j-1); 028 } 029 } 030 031 032 // exchange a[i] and a[j] 033 private static void exch(String[] a, int i, int j) { 034 String swap = a[i]; 035 a[i] = a[j]; 036 a[j] = swap; 037 } 038 039 // is v < w ? 040 private static boolean less(String v, String w) { 041 return (v.compareTo(w) < 0); 042 } 043 044 // 045 private static void draw(String[] a, int row, int ith, int jth) { 046 StdDraw.setPenColor(StdDraw.BLACK); 047 StdDraw.text(-2.50, row, ith + ""); 048 StdDraw.text(-1.25, row, jth + ""); 049 for (int i = 0; i < a.length; i++) { 050 if (i == jth) StdDraw.setPenColor(StdDraw.BOOK_RED); 051 else if (i < jth) StdDraw.setPenColor(StdDraw.BLACK); 052 else StdDraw.setPenColor(StdDraw.LIGHT_GRAY); 053 StdDraw.text(i, row, a[i]); 054 } 055 } 056 057 // display header 058 private static void header(String[] a) { 059 int N = a.length; 060 061 StdDraw.setPenColor(StdDraw.BLACK); 062 StdDraw.text(N/2, -3, "a[ ]"); 063 for (int i = 0; i < N; i++) 064 StdDraw.text(i, -2, i + ""); 065 StdDraw.text(-2.50, -2, "i"); 066 StdDraw.text(-1.25, -2, "j"); 067 StdDraw.setPenColor(StdDraw.BOOK_RED); 068 StdDraw.line(-3, -1.65, N-.5, -1.65); 069 StdDraw.setPenColor(StdDraw.BLACK); 070 for (int i = 0; i < a.length; i++) 071 StdDraw.text(i, -1, a[i]); 072 } 073 074 // display footer 075 private static void footer(String[] a) { 076 int N = a.length; 077 StdDraw.setPenColor(StdDraw.BLACK); 078 for (int i = 0; i < a.length; i++) 079 StdDraw.text(i, N, a[i]); 080 } 081 082 083 084 // test client 085 public static void main(String[] args) { 086 // parse command-line argument as an array of 1-character strings 087 //args = new String[] { "9876543210" }; 088 args = new String[] { "SORTEXAMPLE" }; 089 090 String s = args[0]; 091 int N = s.length(); 092 String[] a = ArrayGenerator.fromString (s); 093 094 // set canvas size 095 StdDraw.setCanvasSize(30*(N+3), 30*(N+3)); 096 StdDraw.setXscale(-3, N+1); 097 StdDraw.setYscale(N+1, -3); 098 StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 13)); 099 100 // draw the header 101 header(a); 102 103 // sort the array 104 sort(a); 105 106 // draw the footer 107 footer(a); 108 } 109 110}