/*****************************************************************************/ /* */ /* Bubble Sort Program: Graphical Version */ /* */ /* March 1998, Toshimi Minoura */ /* */ /*****************************************************************************/ // Numbers in array data[] are sorted by bubble sort. // Array elements data[i] such that i <= ceilingIdx are sorted. // Elements data[i-1] and data[i] are compared, and they are exchanged // if data[i-1] > data[i]. import java.awt.*; import java.util.*; // for StringTokenizer class BubbleSortG extends StepTestCanvas { // data0[] provides initial data to be sorted private int data0[] = { 17, 10, 8, 13, 15, 4, 6, 20, 15, 18 }; int[] data1 = new int[100]; // values converted from input int inputSize; // # of values in data1[]; private int data[] = null; // sorted data private int ceilingIdx; // index of last sorted element private int currentIdx; // index to slot pointed by arrow private int currentIdx2; // index to another highlighted slot public BubbleSortG() { // constructor data1 = new int[data0.length]; for (int i = 0; i < data0.length; i++) { // copy data0[] to data1[] data1[i] = data0[i]; }; inputSize = data0.length; } public void dataPrint() { // print array content System.out.print("daraPrint(): ceilingIdx = " + ceilingIdx + ", data = "); for (int i = 0; i < data.length; i++) { System.out.print(data[i]); // print every value in data[] if (i < data.length - 1) System.out.print(", "); }; System.out.println(""); } public void drawRightArrow(Graphics g, int x1, int y1, int x2) { Polygon poly = new Polygon(); poly.addPoint(x1, y1 - 2); poly.addPoint(x1, y1 + 2); poly.addPoint(x2 - 6, y1 + 2); poly.addPoint(x2 - 6, y1 + 6); poly.addPoint(x2, y1); poly.addPoint(x2 - 6, y1 - 6); poly.addPoint(x2 - 6, y1 - 2); g.fillPolygon(poly); // draw arrow } static final int ArrayXLoc = 130; // left position of array static final int ArrayYLoc = 20; // top position of array static final int ArrowXLoc = 50; // left position of arrow static final int UnitWidth = 200; // unit width for value 10 static final int ArrowWidth = 50; // width of arrow static final int SlotHeight = 30; // height of array field static Color BoxColor = new Color(100, 0, 100); // for box outline static Color UnsortedColor = new Color(0, 150, 0); // for unsorted values static Color ArrowColor = new Color(0, 0, 200); // for arrow static Color CurrentColor = Color.cyan; // for highlighted slots static Color SortedColor = new Color(150, 0, 200); // for sorted values static Color StringColor1 = Color.white; static Color StringColor2 = Color.black; static String message1 = "Provide values to be sorted."; static String message2 = "If not, default values will be used."; public synchronized void paint(Graphics g) { // public void paint(Graphics g) { System.out.println("paint() entered."); if (data == null) { // initial screen // display initial message at int stringWidth = g.getFontMetrics().stringWidth(message2); int stringXLoc = (canvasWidth - stringWidth) / 2; int stringYLoc = canvasHeight * 2 / 5; g.drawString(message1, stringXLoc, stringYLoc); g.drawString(message2, stringXLoc, stringYLoc + 30); return; } if (currentIdx != -1) { // is sorting in progress? int y2 = ArrayYLoc + currentIdx * SlotHeight; // y position of arrow g.setColor(ArrowColor); // prepare to draw arrow drawRightArrow(g, ArrowXLoc + 2, y2 + 10, ArrowXLoc + ArrowWidth); } if (ceilingIdx != -1) { // is sorting in progress? int y2 = ArrayYLoc + ceilingIdx * SlotHeight; // y position of ceiling g.setColor(BoxColor); // prepare to draw ceiling label g.drawString("ceilingIdx", ArrowXLoc - 8, y2 + 14); } int y = ArrayYLoc; // top position of current slot for (int i = 0; i < data.length; i ++) { g.setColor(StringColor2); if (i < 10) { g.drawString("" + i, ArrayXLoc - 20, y + 14); } else { g.drawString("" + i, ArrayXLoc - 25, y + 14); } g.setColor(BoxColor); int barWidth = data[i] * UnitWidth / 10; // compute bar length g.drawRect(ArrayXLoc, y, barWidth, SlotHeight - 10); // draw element if (i <= ceilingIdx) { // element sorted? g.setColor(SortedColor); // yes } else if (i == currentIdx || i == currentIdx2) { g.setColor(CurrentColor); // highlight color } else { g.setColor(UnsortedColor); // no } g.fillRect(ArrayXLoc + 2, y + 2, barWidth - 3, SlotHeight - 13); if (i == currentIdx || i == currentIdx2) { g.setColor(StringColor2); } else { g.setColor(StringColor1); } g.drawString(String.valueOf(data[i]), ArrayXLoc + 10, y + 14); y += SlotHeight; // update y position to next array element } } public static void main(String argv[]) { new StepTestFrame("Bubble Sort", new BubbleSortG(), 600, 460).show(); } // Operations that manipulate data within runMain() should be synchronized // because there is a small possibility for those data to be accessed // by paint() while they are being modified. This synchonization is not // done. To do that with Java's synchorization statements is not easy. // The lock should be released only within repaint(). public void runMain() { // called from run() of StepTestCanvas System.out.println("BubbleSortG.runMain() entered"); data = null; // discard sorted data ceilingIdx = -1; // all values in data unsorted currentIdx = -1; // no need to display arrow currentIdx2 = -1; // no need to highlight element to be sapped repaintStep(); StringTokenizer inputTokens = getInputTokens(); int i = 0; while (inputTokens.hasMoreTokens()) { // input not exhausted data1[i] = Integer.parseInt(inputTokens.nextToken()); // get next value i++; } if (i > 0) { // if there are input values, inputSize = i; // use new values; otherwise, use old ones }; data = new int[inputSize]; // copy initial values to data[] for (int j = 0; j < inputSize; j++) { data[j] = data1[j]; } repaintStep("Bubble sort will start with the values displayed."); dataPrint(); ceilingIdx = -1; for ( ; ceilingIdx < data.length - 1; ) { currentIdx = data.length - 1; for ( ; currentIdx > ceilingIdx + 1; ) { currentIdx2 = currentIdx - 1; // another slot highlighted repaintStep("Values " + data[currentIdx] + " and " + data[currentIdx - 1] + " are compared."); currentIdx--; currentIdx2 = currentIdx + 1; // another slot highlighted if (data[currentIdx + 1] < data[currentIdx]) { // out of order? int temp = data[currentIdx + 1]; data[currentIdx + 1] = data[currentIdx]; // sawp values data[currentIdx] = temp; repaintStep("Values " + data[currentIdx] + " and " + data[currentIdx + 1] + " were exchanged."); } else { // no, continue to move up for insertion point repaintStep("Values " + data[currentIdx] + " and " + data[currentIdx + 1] + " are right order."); } } currentIdx = currentIdx2 = -2; ceilingIdx++; // additional element got sorted dataPrint(); repaintStep("Bubbling to slot " + ceilingIdx + " done."); } currentIdx = -1; // no current data repaintStep("Sorting completed."); System.out.println("runMain() completed"); } public void stop() { System.out.println("BubbleSortG.stop() entered."); data = null; super.stop(); // terminate Thread } }