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}