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}