001package algs21;
002import stdlib.*;
003import java.awt.Font;
004/* ***********************************************************************
005 *  Compilation:  javac ZShellBars.java
006 *  Execution:    java ZShellBars N
007 *  Dependencies: StdDraw.java
008 *
009 *  Shellsor N random real numbers between 0 and 1, visualizing
010 *  the results by ploting bars with heights proportional to the values.
011 *
012 *  % java ZShellBars 150
013 *
014 *************************************************************************/
015
016public class XBarsShell {
017        private static final int FF = 4;
018
019
020        public static void sort(double[] a) {
021                int N = a.length;
022                int k = 1;
023                int h = 1;
024                while (h < N/3) {
025                        h = 3*h + 1;
026                        k++;
027                }
028                show(a, k, "input");
029
030                while (h >= 1) {
031                        for (int i = h; i < N; i++) {
032                                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
033                                        exch(a, j, j-h);
034                                }
035                        }
036                        if (h < N) show(a, --k, h + "-sorted");
037                        h = h/3;
038                }
039        }
040
041        private static void show(double[] a, int k, String message) {
042                for (int i = 0; i < a.length; i++) {
043                        StdDraw.setPenColor(StdDraw.BLACK);
044                        StdDraw.line(i, FF*k, i, FF*k + a[i]*(FF-1));
045                }
046                StdDraw.setPenColor(StdDraw.BOOK_RED);
047                StdDraw.text(0, FF*k - .3, message);
048        }
049
050        private static boolean less(double v, double w) {
051                return v < w;
052        }
053
054        private static void exch(double[] a, int i, int j) {
055                double t = a[i];
056                a[i] = a[j];
057                a[j] = t;
058        }
059
060
061        public static void main(String[] args) {
062                args = new String[] { "120" };
063                int N = Integer.parseInt(args[0]);
064                int k = (int) Math.round(Math.log(N) / Math.log(3));
065                StdDraw.show(0);
066                StdDraw.setCanvasSize(756, 900);
067                StdDraw.setFont(new Font("SansSerif", Font.PLAIN, 9));
068                StdDraw.setXscale(-1, N+1);
069                StdDraw.setYscale(-1, (1+FF)*k);
070                StdDraw.setPenRadius(.005);
071                sort (ArrayGenerator.doubleRandomUnique (N));
072                //sort (ArrayGenerator.partiallySortedUnique (N));
073                //sort (ArrayGenerator.sortedUnique (N));
074                //sort (ArrayGenerator.reverseSortedUnique (N));
075                StdDraw.show(0);
076        }
077}