#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    37
    Rep Power
    5

    Convert text file to bar graph


    So I'm support to convert an Insertion and Selection sort to sorted bars, but I keep using a completely incorrect method.

    From Algorithms, 4th edition by Sedgewick and Wayne:

    "Add code to Insertion and Selection to make them draw the array contents as vertical bars like the visual traces in this section, redrawing the bars after each pass, to produce an animated effect, ending in a “sorted” picture where the bars appear in order of their height. "

    The problem is that I have no idea how to implement this.

    Here is the Insertion sort:

    Code:
    import java.util.Comparator;
    
    public class Insertion {
    
        // use natural order and Comparable interface
        public static void sort(Comparable[] a) {
            int N = a.length;
            for (int i = 0; i < N; i++) {
                for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
                    exch(a, j, j-1);
                }
                assert isSorted(a, 0, i);
            }
            assert isSorted(a);
        }
    
        // use a custom order and Comparator interface - see Section 3.5
        public static void sort(Object[] a, Comparator c) {
            int N = a.length;
            for (int i = 0; i < N; i++) {
                for (int j = i; j > 0 && less(c, a[j], a[j-1]); j--) {
                    exch(a, j, j-1);
                }
                assert isSorted(a, c, 0, i);
            }
            assert isSorted(a, c);
        }
    
        // return a permutation that gives the elements in a[] in ascending order
        // do not change the original array a[]
        public static int[] indexSort(Comparable[] a) {
            int N = a.length;
            int[] index = new int[N];
            for (int i = 0; i < N; i++)
                index[i] = i;
    
            for (int i = 0; i < N; i++)
                for (int j = i; j > 0 && less(a[index[j]], a[index[j-1]]); j--)
                    exch(index, j, j-1);
    
            return index;
        }
    
       /***********************************************************************
        *  Helper sorting functions
        ***********************************************************************/
        
        // is v < w ?
        private static boolean less(Comparable v, Comparable w) {
            return (v.compareTo(w) < 0);
        }
    
        // is v < w ?
        private static boolean less(Comparator c, Object v, Object w) {
            return (c.compare(v, w) < 0);
        }
            
        // exchange a[i] and a[j]
        private static void exch(Object[] a, int i, int j) {
            Object swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    
        // exchange a[i] and a[j]  (for indirect sort)
        private static void exch(int[] a, int i, int j) {
            int swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    
       /***********************************************************************
        *  Check if array is sorted - useful for debugging
        ***********************************************************************/
        private static boolean isSorted(Comparable[] a) {
            return isSorted(a, 0, a.length - 1);
        }
    
        // is the array sorted from a[lo] to a[hi]
        private static boolean isSorted(Comparable[] a, int lo, int hi) {
            for (int i = lo + 1; i <= hi; i++)
                if (less(a[i], a[i-1])) return false;
            return true;
        }
    
        private static boolean isSorted(Object[] a, Comparator c) {
            return isSorted(a, c, 0, a.length - 1);
        }
    
        // is the array sorted from a[lo] to a[hi]
        private static boolean isSorted(Object[] a, Comparator c, int lo, int hi) {
            for (int i = lo + 1; i <= hi; i++)
                if (less(c, a[i], a[i-1])) return false;
            return true;
        }
    
       // print array to standard output
        private static void show(Comparable[] a) {
            for (int i = 0; i < a.length; i++) {
                StdOut.println(a[i]);
            }
        }
    
        // Read strings from standard input, sort them, and print.
        public static void main(String[] args) {
            String[] a = StdIn.readStrings();
            Insertion.sort(a);
            show(a);
        }
    }
    Here is the selection sort:

    Code:
    import java.util.Comparator;
    
    public class Selection {
    
        // selection sort
        public static void sort(Comparable[] a) {
            int N = a.length;
            for (int i = 0; i < N; i++) {
                int min = i;
                for (int j = i+1; j < N; j++) {
                    if (less(a[j], a[min])) min = j;
                }
                exch(a, i, min);
                assert isSorted(a, 0, i);
            }
            assert isSorted(a);
        }
    
        // use a custom order and Comparator interface - see Section 3.5
        public static void sort(Object[] a, Comparator c) {
            int N = a.length;
            for (int i = 0; i < N; i++) {
                int min = i;
                for (int j = i+1; j < N; j++) {
                    if (less(c, a[j], a[min])) min = j;
                }
                exch(a, i, min);
                assert isSorted(a, c, 0, i);
            }
            assert isSorted(a, c);
        }
    
    
       /***********************************************************************
        *  Helper sorting functions
        ***********************************************************************/
        
        // is v < w ?
        private static boolean less(Comparable v, Comparable w) {
            return (v.compareTo(w) < 0);
        }
    
        // is v < w ?
        private static boolean less(Comparator c, Object v, Object w) {
            return (c.compare(v, w) < 0);
        }
            
            
        // exchange a[i] and a[j]
        private static void exch(Object[] a, int i, int j) {
            Object swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    
    
       /***********************************************************************
        *  Check if array is sorted - useful for debugging
        ***********************************************************************/
    
        // is the array a[] sorted?
        private static boolean isSorted(Comparable[] a) {
            return isSorted(a, 0, a.length - 1);
        }
            
        // is the array sorted from a[lo] to a[hi]
        private static boolean isSorted(Comparable[] a, int lo, int hi) {
            for (int i = lo + 1; i <= hi; i++)
                if (less(a[i], a[i-1])) return false;
            return true;
        }
    
        // is the array a[] sorted?
        private static boolean isSorted(Object[] a, Comparator c) {
            return isSorted(a, c, 0, a.length - 1);
        }
    
        // is the array sorted from a[lo] to a[hi]
        private static boolean isSorted(Object[] a, Comparator c, int lo, int hi) {
            for (int i = lo + 1; i <= hi; i++)
                if (less(c, a[i], a[i-1])) return false;
            return true;
        }
    
    
    
        // print array to standard output
        private static void show(Comparable[] a) {
            for (int i = 0; i < a.length; i++) {
                StdOut.println(a[i]);
            }
        }
    
        // Read strings from standard input, sort them, and print.
        public static void main(String[] args) {
            String[] a = StdIn.readStrings();
            Selection.sort(a);
            show(a);
        }
    }
    Here is StdOut:

    Code:
    import java.io.OutputStreamWriter;
    import java.io.PrintWriter;
    import java.io.UnsupportedEncodingException;
    import java.util.Locale;
    
    /**
     *  <i>Standard output</i>. This class provides methods for writing strings
     *  and numbers to standard output.
     *  <p>
     *  For additional documentation, see <a href="http://introcs.cs.princeton.edu/15inout">Section 1.5</a> of
     *  <i>Introduction to Programming in Java: An Interdisciplinary Approach</i> by Robert Sedgewick and Kevin Wayne.
     */
    public final class StdOut {
    
        // force Unicode UTF-8 encoding; otherwise it's system dependent
        private static final String charsetName = "UTF-8";
    
        // assume language = English, country = US for consistency with StdIn
        private static final Locale US_LOCALE = new Locale("en", "US");
    
        // send output here
        private static PrintWriter out;
    
        // this is called before invoking any methods
        static {
            try {
                out = new PrintWriter(new OutputStreamWriter(System.out, charsetName), true);
            }
            catch (UnsupportedEncodingException e) { System.out.println(e); }
        }
    
        // don't instantiate
        private StdOut() { }
    
        // close the output stream (not required)
       /**
         * Close standard output.
         */
        public static void close() {
            out.close();
        }
    
       /**
         * Terminate the current line by printing the line separator string.
         */
        public static void println() {
            out.println();
        }
    
       /**
         * Print an object to standard output and then terminate the line.
         */
        public static void println(Object x) {
            out.println(x);
        }
    
       /**
         * Print a boolean to standard output and then terminate the line.
         */
        public static void println(boolean x) {
            out.println(x);
        }
    
       /**
         * Print a char to standard output and then terminate the line.
         */
        public static void println(char x) {
            out.println(x);
        }
    
       /**
         * Print a double to standard output and then terminate the line.
         */
        public static void println(double x) {
            out.println(x);
        }
    
       /**
         * Print a float to standard output and then terminate the line.
         */
        public static void println(float x) {
            out.println(x);
        }
    
       /**
         * Print an int to standard output and then terminate the line.
         */
        public static void println(int x) {
            out.println(x);
        }
    
       /**
         * Print a long to standard output and then terminate the line.
         */
        public static void println(long x) {
            out.println(x);
        }
    
       /**
         * Print a short to standard output and then terminate the line.
         */
        public static void println(short x) {
            out.println(x);
        }
    
       /**
         * Print a byte to standard output and then terminate the line.
         */
        public static void println(byte x) {
            out.println(x);
        }
    
       /**
         * Flush standard output.
         */
        public static void print() {
            out.flush();
        }
    
       /**
         * Print an Object to standard output and flush standard output.
         */
        public static void print(Object x) {
            out.print(x);
            out.flush();
        }
    
       /**
         * Print a boolean to standard output and flush standard output.
         */
        public static void print(boolean x) {
            out.print(x);
            out.flush();
        }
    
       /**
         * Print a char to standard output and flush standard output.
         */
        public static void print(char x) {
            out.print(x);
            out.flush();
        }
    
       /**
         * Print a double to standard output and flush standard output.
         */
        public static void print(double x) {
            out.print(x);
            out.flush();
        }
    
       /**
         * Print a float to standard output and flush standard output.
         */
        public static void print(float x) {
            out.print(x);
            out.flush();
        }
    
       /**
         * Print an int to standard output and flush standard output.
         */
        public static void print(int x) {
            out.print(x);
            out.flush();
        }
    
       /**
         * Print a long to standard output and flush standard output.
         */
        public static void print(long x) {
            out.print(x);
            out.flush();
        }
    
       /**
         * Print a short to standard output and flush standard output.
         */
        public static void print(short x) {
            out.print(x);
            out.flush();
        }
    
       /**
         * Print a byte to standard output and flush standard output.
         */
        public static void print(byte x) {
            out.print(x);
            out.flush();
        }
    
       /**
         * Print a formatted string to standard output using the specified
         * format string and arguments, and flush standard output.
         */
        public static void printf(String format, Object... args) {
            out.printf(US_LOCALE, format, args);
            out.flush();
        }
    
       /**
         * Print a formatted string to standard output using the specified
         * locale, format string, and arguments, and flush standard output.
         */
        public static void printf(Locale locale, String format, Object... args) {
            out.printf(locale, format, args);
            out.flush();
        }
    
        // This method is just here to test the class
        public static void main(String[] args) {
    
            // write to stdout
            StdOut.println("Test");
            StdOut.println(17);
            StdOut.println(true);
            StdOut.printf("%.6f\n", 1.0/7.0);
        }
    
    }
    Here is StdIn:

    Code:
    import java.util.Scanner;
    import java.util.regex.Pattern;
    
    /**
     *  <i>Standard input</i>. This class provides methods for reading strings
     *  and numbers from standard input. See 
     *  <a href="http://introcs.cs.princeton.edu/15inout">Section 1.5</a> of
     *  <i>Introduction to Programming in Java: An Interdisciplinary Approach</i>
     *  by Robert Sedgewick and Kevin Wayne.
     *  <p>
     *  See the technical information in the documentation of the {@link In}
     *  class, which applies to this class as well. 
     */
    public final class StdIn {
    
        // it doesn't make sense to instantiate this class
        private StdIn() {}
    
        private static Scanner scanner;
     
        /*** begin: section (1 of 2) of code duplicated from In to StdIn */
        
        // assume Unicode UTF-8 encoding
        private static final String charsetName = "UTF-8";
    
        // assume language = English, country = US for consistency with System.out.
        private static final java.util.Locale usLocale = 
            new java.util.Locale("en", "US");
    
        // the default token separator; we maintain the invariant that this value 
        // is held by the scanner's delimiter between calls
        private static final Pattern WHITESPACE_PATTERN
            = Pattern.compile("\\p{javaWhitespace}+");
    
        // makes whitespace characters significant 
        private static final Pattern EMPTY_PATTERN
            = Pattern.compile("");
    
        // used to read the entire input. source:
        // http://weblogs.java.net/blog/pat/archive/2004/10/stupid_scanner_1.html
        private static final Pattern EVERYTHING_PATTERN
            = Pattern.compile("\\A");
    
        /*** end: section (1 of 2) of code duplicated from In to StdIn */
    
        /*** begin: section (2 of 2) of code duplicated from In to StdIn,
          *  with all methods changed from "public" to "public static" ***/
    
       /**
         * Is the input empty (except possibly for whitespace)? Use this
         * to know whether the next call to {@link #readString()}, 
         * {@link #readDouble()}, etc will succeed.
         */
        public static boolean isEmpty() {
            return !scanner.hasNext();
        }
    
       /**
         * Does the input have a next line? Use this to know whether the
         * next call to {@link #readLine()} will succeed. <p> Functionally
         * equivalent to {@link #hasNextChar()}.
         */
        public static boolean hasNextLine() {
            return scanner.hasNextLine();
        }
    
        /**
         * Is the input empty (including whitespace)? Use this to know 
         * whether the next call to {@link #readChar()} will succeed. <p> Functionally
         * equivalent to {@link #hasNextLine()}.
         */
        public static boolean hasNextChar() {
            scanner.useDelimiter(EMPTY_PATTERN);
            boolean result = scanner.hasNext();
            scanner.useDelimiter(WHITESPACE_PATTERN);
            return result;
        }
    
    
       /**
         * Read and return the next line.
         */
        public static String readLine() {
            String line;
            try                 { line = scanner.nextLine(); }
            catch (Exception e) { line = null;               }
            return line;
        }
    
        /**
         * Read and return the next character.
         */
        public static char readChar() {
            scanner.useDelimiter(EMPTY_PATTERN);
            String ch = scanner.next();
            assert (ch.length() == 1) : "Internal (Std)In.readChar() error!"
                + " Please contact the authors.";
            scanner.useDelimiter(WHITESPACE_PATTERN);
            return ch.charAt(0);
        }  
    
    
       /**
         * Read and return the remainder of the input as a string.
         */
        public static String readAll() {
            if (!scanner.hasNextLine())
                return "";
    
            String result = scanner.useDelimiter(EVERYTHING_PATTERN).next();
            // not that important to reset delimeter, since now scanner is empty
            scanner.useDelimiter(WHITESPACE_PATTERN); // but let's do it anyway
            return result;
        }
    
    
       /**
         * Read and return the next string.
         */
        public static String readString() {
            return scanner.next();
        }
    
       /**
         * Read and return the next int.
         */
        public static int readInt() {
            return scanner.nextInt();
        }
    
       /**
         * Read and return the next double.
         */
        public static double readDouble() {
            return scanner.nextDouble();
        }
    
       /**
         * Read and return the next float.
         */
        public static float readFloat() {
            return scanner.nextFloat();
        }
    
       /**
         * Read and return the next long.
         */
        public static long readLong() {
            return scanner.nextLong();
        }
    
       /**
         * Read and return the next short.
         */
        public static short readShort() {
            return scanner.nextShort();
        }
    
       /**
         * Read and return the next byte.
         */
        public static byte readByte() {
            return scanner.nextByte();
        }
    
        /**
         * Read and return the next boolean, allowing case-insensitive
         * "true" or "1" for true, and "false" or "0" for false.
         */
        public static boolean readBoolean() {
            String s = readString();
            if (s.equalsIgnoreCase("true"))  return true;
            if (s.equalsIgnoreCase("false")) return false;
            if (s.equals("1"))               return true;
            if (s.equals("0"))               return false;
            throw new java.util.InputMismatchException();
        }
    
        /**
         * Read all strings until the end of input is reached, and return them.
         */
        public static String[] readAllStrings() {
            // we could use readAll.trim().split(), but that's not consistent
            // since trim() uses characters 0x00..0x20 as whitespace
            String[] tokens = WHITESPACE_PATTERN.split(readAll());
            if (tokens.length == 0 || tokens[0].length() > 0)
                return tokens;
            String[] decapitokens = new String[tokens.length-1];
            for (int i=0; i < tokens.length-1; i++)
                decapitokens[i] = tokens[i+1];
            return decapitokens;
        }
    
        /**
         * Read all ints until the end of input is reached, and return them.
         */
        public static int[] readAllInts() {
            String[] fields = readAllStrings();
            int[] vals = new int[fields.length];
            for (int i = 0; i < fields.length; i++)
                vals[i] = Integer.parseInt(fields[i]);
            return vals;
        }
    
        /**
         * Read all doubles until the end of input is reached, and return them.
         */
        public static double[] readAllDoubles() {
            String[] fields = readAllStrings();
            double[] vals = new double[fields.length];
            for (int i = 0; i < fields.length; i++)
                vals[i] = Double.parseDouble(fields[i]);
            return vals;
        }
        
        /*** end: section (2 of 2) of code duplicated from In to StdIn */
        
        
        /**
         * If StdIn changes, use this to reinitialize the scanner.
         */
        private static void resync() {
            setScanner(new Scanner(new java.io.BufferedInputStream(System.in), 
                                   charsetName));
        }
        
        private static void setScanner(Scanner scanner) {
            StdIn.scanner = scanner;
            StdIn.scanner.useLocale(usLocale);
        }
    
        // do this once when StdIn is initialized
        static {
            resync();
        }
    
       /**
         * Reads all ints from stdin.
         * @deprecated For more consistency, use {@link #readAllInts()}
         */
        public static int[] readInts() {
            return readAllInts();
        }
    
       /**
         * Reads all doubles from stdin.
         * @deprecated For more consistency, use {@link #readAllDoubles()}
         */
        public static double[] readDoubles() {
            return readAllDoubles();
        }
    
       /**
         * Reads all Strings from stdin.
         * @deprecated For more consistency, use {@link #readAllStrings()}
         */
        public static String[] readStrings() {
            return readAllStrings();
        }
    
    
        /**
         * Interactive test of basic functionality.
         */
        public static void main(String[] args) {
    
            System.out.println("Type a string: ");
            String s = StdIn.readString();
            System.out.println("Your string was: " + s);
            System.out.println();
    
            System.out.println("Type an int: ");
            int a = StdIn.readInt();
            System.out.println("Your int was: " + a);
            System.out.println();
    
            System.out.println("Type a boolean: ");
            boolean b = StdIn.readBoolean();
            System.out.println("Your boolean was: " + b);
            System.out.println();
    
            System.out.println("Type a double: ");
            double c = StdIn.readDouble();
            System.out.println("Your double was: " + c);
            System.out.println();
    
        }
    
    }
    A couple of hints have been suggested, but I don't know how to implement them.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    37
    Rep Power
    5
    I figured it out. No need to post on this now.

IMN logo majestic logo threadwatch logo seochat tools logo