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}