001package algs21; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac ZInsertionBars.java 005 * Execution: java ZInsertionBars N 006 * Dependencies: StdDraw.java 007 * 008 * Insertion sort N random real numbers between 0 and 1, visualizing 009 * the results by ploting bars with heights proportional to the values. 010 * 011 * % java ZInsertionBars 20 012 * 013 *************************************************************************/ 014 015 016public class XBarsInsertion { 017 public static void sort(double[] a) { 018 int N = a.length; 019 for (int i = 0; i < N; i++) { 020 int j = i; 021 while (j >= 1 && less(a[j], a[j-1])) { 022 exch(a, j, j-1); 023 j--; 024 } 025 show(a, i, j); 026 } 027 } 028 029 private static void show(double[] a, int i, int j) { 030 StdDraw.setYscale(-a.length + i + 1, i); 031 StdDraw.setPenColor(StdDraw.LIGHT_GRAY); 032 for (int k = 0; k < j; k++) 033 StdDraw.line(k, 0, k, a[k]*.6); 034 StdDraw.setPenColor(StdDraw.BOOK_RED); 035 StdDraw.line(j, 0, j, a[j]*.6); 036 StdDraw.setPenColor(StdDraw.BLACK); 037 for (int k = j+1; k <= i; k++) 038 StdDraw.line(k, 0, k, a[k]*.6); 039 StdDraw.setPenColor(StdDraw.LIGHT_GRAY); 040 for (int k = i+1; k < a.length; k++) 041 StdDraw.line(k, 0, k, a[k]*.6); 042 } 043 044 private static boolean less(double v, double w) { 045 return v < w; 046 } 047 048 private static void exch(double[] a, int i, int j) { 049 double t = a[i]; 050 a[i] = a[j]; 051 a[j] = t; 052 } 053 054 public static void main(String[] args) { 055 args = new String[] { "10" }; 056 057 int N = Integer.parseInt(args[0]); 058 StdDraw.setCanvasSize(N*8, N*32); 059 StdDraw.setXscale(-1, N+1); 060 StdDraw.setPenRadius(.006); 061 sort (ArrayGenerator.doubleRandomUnique (N)); 062 //sort (ArrayGenerator.partiallySortedUnique (N)); 063 //sort (ArrayGenerator.sortedUnique (N)); 064 //sort (ArrayGenerator.reverseSortedUnique (N)); 065 } 066 067}