001package algs23;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac ZQuick3wayBars.java
005 *  Execution:    java ZQuick3wayBars N M
006 *  Dependencies: StdDraw.java
007 *
008 *  Sort N random integers between 1 and M using quicksort with 3-way
009 *  partitioning, visualizing the results by ploting bars with
010 *  heights proportional to the values.
011 *
012 *  % java ZQuick3wayBars 20
013 *
014 *************************************************************************/
015
016public class XBarsQuick3way {
017        private static int N, M;
018        private static int frame = 0;
019
020        public static void sort(double[] a) {
021                // StdRandom.shuffle(a);
022                show(a, 0, 0, -1, a.length-1); frame++;
023                sort(a, 0, a.length - 1);
024                show(a, 0, 0, -1, a.length-1); frame++;
025        }
026
027        private static void sort(double[] a, int lo, int hi) {
028                if (hi <= lo) return;
029                int lt = lo, gt = hi;
030                double v = a[lo];
031                int i = lo;
032                while (i <= gt)
033                        if      (less(v, a[i])) exch(a, i, gt--);
034                        else if (less(a[i], v)) exch(a, lt++, i++);
035                        else                    i++;
036                show(a, lo, lt, gt, hi); frame++;
037                sort(a, lo, lt - 1);
038                sort(a, gt + 1, hi);
039        }
040
041        private static boolean less(double v, double w) {
042                return v < w;
043        }
044
045        private static void exch(double[] a, int i, int j) {
046                double t = a[i];
047                a[i] = a[j];
048                a[j] = t;
049        }
050
051        private static void show(double[] a, int lo, int lt, int gt, int hi) {
052                StdDraw.setYscale(-(M+1)*(M+1-frame), (M+1)*frame + (M+1)/2);
053                StdDraw.setPenColor(StdDraw.LIGHT_GRAY);
054                for (int k = 0; k < lo; k++)
055                        StdDraw.line(k, 0, k, a[k]*.7);
056                for (int k = hi+1; k < a.length; k++)
057                        StdDraw.line(k, 0, k, a[k]*.7);
058                StdDraw.setPenColor(StdDraw.BLACK);
059                for (int k = lo; k <= hi; k++)
060                        StdDraw.line(k, 0, k, a[k]*.7);
061                StdDraw.setPenColor(StdDraw.BOOK_RED);
062                for (int k = lt; k <= gt; k++)
063                        StdDraw.line(k, 0, k, a[k]*.7);
064        }
065
066        public static void main(String[] args) {
067                args = new String[] { "120", "10" };
068                N = Integer.parseInt(args[0]);
069                M = Integer.parseInt(args[1]);
070                StdDraw.setCanvasSize(800, M*70);
071                StdDraw.show(0);
072                StdDraw.setXscale(-1, N+1);
073                StdDraw.setPenRadius(.006);
074                StdDraw.show(0);
075                double[] a = new double[N];
076                for (int i = 0; i < N; i++)
077                        a[i] = 1 + (int) (Math.random() * M);
078                sort(a);
079                StdDraw.show(0);
080        }
081}