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