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