001package algs21; 002import stdlib.*; 003 004public class XAnimatedInsertion { 005 006 public static void sort (double[] a) { 007 int N = a.length; 008 show (a, 0, 0); 009 for (int i = 0; i < N; i++) { 010 for (int j = i; j > 0 && less (a[j], a[j - 1]); j--) { 011 exch (a, j, j - 1); 012 show (a, i, j - 1); 013 } 014 assert isSorted (a, 0, i); 015 } 016 assert isSorted (a); 017 } 018 019 private static void show (double[] a, int i, int min) { 020 StdDraw.clear (); 021 //StdDraw.setYscale(-a.length + i + 1, i); 022 StdDraw.setPenColor (StdDraw.LIGHT_GRAY); 023 for (int k = 0; k < i; k++) 024 StdDraw.line (k, 0, k, a[k]); 025 StdDraw.setPenColor (StdDraw.BLACK); 026 for (int k = i; k < a.length; k++) 027 StdDraw.line (k, 0, k, a[k]); 028 StdDraw.setPenColor (StdDraw.BOOK_RED); 029 StdDraw.line (min, 0, min, a[min]); 030 StdDraw.show (100); 031 } 032 033 private static boolean less (double v, double w) { 034 return v < w; 035 } 036 private static void exch (double[] a, int i, int j) { 037 double t = a[i]; 038 a[i] = a[j]; 039 a[j] = t; 040 } 041 private static boolean isSorted (double[] a) { 042 return isSorted (a, 0, a.length - 1); 043 } 044 private static boolean isSorted (double[] a, int lo, int hi) { 045 for (int i = lo + 1; i <= hi; i++) 046 if (less (a[i], a[i - 1])) return false; 047 return true; 048 } 049 050 public static void main (String[] args) { 051 args = new String[] { "25" }; 052 int N = Integer.parseInt (args[0]); 053 StdDraw.setCanvasSize (N*7, 320); 054 StdDraw.setXscale (-1, N + 1); 055 StdDraw.setPenRadius (.006); 056 sort (ArrayGenerator.doublePartiallySortedUnique (N)); 057 sort (ArrayGenerator.doubleRandomUnique (N)); 058 sort (ArrayGenerator.doubleSortedUnique (N)); 059 sort (ArrayGenerator.doubleReverseSortedUnique (N)); 060 } 061 062}