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);
  }
}