``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ``` ```package algs23; import stdlib.*; /* *********************************************************************** * Compilation: javac ZQuick3wayBars.java * Execution: java ZQuick3wayBars N M * Dependencies: StdDraw.java * * Sort N random integers between 1 and M using quicksort with 3-way * partitioning, visualizing the results by ploting bars with * heights proportional to the values. * * % java ZQuick3wayBars 20 * *************************************************************************/ public class XBarsQuick3way { private static int N, M; private static int frame = 0; public static void sort(double[] a) { // StdRandom.shuffle(a); show(a, 0, 0, -1, a.length-1); frame++; sort(a, 0, a.length - 1); show(a, 0, 0, -1, a.length-1); frame++; } private static void sort(double[] a, int lo, int hi) { if (hi <= lo) return; int lt = lo, gt = hi; double v = a[lo]; int i = lo; while (i <= gt) if (less(v, a[i])) exch(a, i, gt--); else if (less(a[i], v)) exch(a, lt++, i++); else i++; show(a, lo, lt, gt, hi); frame++; sort(a, lo, lt - 1); sort(a, gt + 1, hi); } private static boolean less(double v, double w) { return v < w; } private static void exch(double[] a, int i, int j) { double t = a[i]; a[i] = a[j]; a[j] = t; } private static void show(double[] a, int lo, int lt, int gt, int hi) { StdDraw.setYscale(-(M+1)*(M+1-frame), (M+1)*frame + (M+1)/2); StdDraw.setPenColor(StdDraw.LIGHT_GRAY); for (int k = 0; k < lo; k++) StdDraw.line(k, 0, k, a[k]*.7); for (int k = hi+1; k < a.length; k++) StdDraw.line(k, 0, k, a[k]*.7); StdDraw.setPenColor(StdDraw.BLACK); for (int k = lo; k <= hi; k++) StdDraw.line(k, 0, k, a[k]*.7); StdDraw.setPenColor(StdDraw.BOOK_RED); for (int k = lt; k <= gt; k++) StdDraw.line(k, 0, k, a[k]*.7); } public static void main(String[] args) { args = new String[] { "120", "10" }; N = Integer.parseInt(args[0]); M = Integer.parseInt(args[1]); StdDraw.setCanvasSize(800, M*70); StdDraw.show(0); StdDraw.setXscale(-1, N+1); StdDraw.setPenRadius(.006); StdDraw.show(0); double[] a = new double[N]; for (int i = 0; i < N; i++) a[i] = 1 + (int) (Math.random() * M); sort(a); StdDraw.show(0); } } ```