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}