Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |
 User Name: Password: Remember me

New Free Tools on Dev Shed!
We're Excited to announce that Dev Shed now has 70 free tools on the site. To learn more, click here!

 Dev Shed Forums Sponsor:
#1
June 27th, 2013, 09:45 AM
 Astrodude
Contributing User

Join Date: Oct 2012
Posts: 37
Time spent in forums: 7 h 37 m 25 sec
Reputation Power: 5
Homework - 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()},
*/
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!"
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)
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() {
}

/**
* Reads all doubles from stdin.
* @deprecated For more consistency, use {@link #readAllDoubles()}
*/
public static double[] readDoubles() {
}

/**
* Reads all Strings from stdin.
* @deprecated For more consistency, use {@link #readAllStrings()}
*/
public static String[] readStrings() {
}

/**
* 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
June 27th, 2013, 11:50 AM
 Astrodude
Contributing User

Join Date: Oct 2012
Posts: 37
Time spent in forums: 7 h 37 m 25 sec
Reputation Power: 5
I figured it out. No need to post on this now.

 Viewing: Dev Shed Forums > Programming Languages > Java Help > Homework - Convert text file to bar graph

## Developer Shed Advertisers and Affiliates

 Thread Tools Search this Thread Search this Thread: Advanced Search Display Modes Rate This Thread Linear Mode Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off
 View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox Forum Jump Please select one User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home -------------------- Programming Languages    PHP Development        PHP FAQs and Stickies    Perl Programming        Perl FAQs and Stickies    C Programming        C Programming FAQs and Stickies    Java Help        Java FAQs    Python Programming        Python Programming FAQs    Ruby Programming        Ruby Programming FAQs    Game Development        Game Development FAQs Programming Languages - More    ASP Programming        ASP Programming FAQs    .Net Development        .Net Development FAQs    Visual Basic Programming        Visual Basic Programming FAQs    Software Design        Software Design FAQs    ColdFusion Development        ColdFusion Development FAQs    Delphi Programming        Delphi Programming FAQs    Regex Programming        Regex Programming FAQs    XML Programming        XML Programming FAQs    Other Programming Languages        Other Programming Languages FAQs Web Design    HTML Programming        HTML Programming FAQs    JavaScript Development        JavaScript Development FAQs    CSS Help        CSS Help FAQs    Flash Help        Flash Help FAQs    Photoshop Help        Photoshop Help FAQs    Web Design Help        Web Design Help FAQs    Website Critiques        Website Critiques FAQs    Search Engine Optimization        Search Engine Optimization FAQs Mobile Programming    Mobile Programming        Mobile Programming FAQs    iPhone SDK Development        iPhone SDK Development FAQs    Android Development        Android Development FAQs    BlackBerry Development        BlackBerry Development FAQs Web Site Management    Business Help        Business Help FAQs    Development Software        Development Software FAQs    Scripts        Scripts FAQs Databases    Database Management        Database Management FAQs    DB2 Development        DB2 Development FAQs    MySQL Help        MySQL Help FAQs    PostgreSQL Help        PostgreSQL Help FAQs    Firebird SQL Development        Firebird SQL Development FAQs    MS SQL Development        MS SQL Development FAQs    Oracle Development        Oracle Development FAQs    LDAP Programming        LDAP Programming FAQs System Administration    Mail Server Help        Mail Server Help FAQs    Apache Development        Apache Development FAQs    Security and Cryptography        Security and Cryptography FAQs    Antivirus Protection        Antivirus Protection FAQs    DNS        DNS FAQs    IIS        IIS FAQs    Networking Help        Networking Help FAQs    FTP Help        FTP Help FAQs Operating Systems    BSD Help        BSD Help FAQs    Linux Help        Linux Help FAQs    UNIX Help        UNIX Help FAQs    Windows Help        Windows Help FAQs    Mac Help        Mac Help FAQs Web Hosting    Web Hosting        Web Hosting FAQs    Free Web Hosting        Free Web Hosting FAQs    Web Hosting Requests        Web Hosting Requests FAQs    Web Hosting Offers        Web Hosting Offers FAQs Computer Hardware    Computer Hardware    CPUs        CPUs FAQs    Cooling        Cooling FAQs    Embedded Programming        Embedded Programming FAQs    Motherboards        Motherboards FAQs    Multimedia Hardware        Multimedia Hardware FAQs Other    Dev Shed Lounge        Dev Shed Lounge FAQs    Development Articles        Development Articles FAQs    Beginner Programming        Beginner Programming FAQs    Hire A Programmer        Hire A Programmer FAQs    Project Help Wanted        Project Help Wanted FAQs Latest News Updated Hourly    Technology News    Business News    Science News Forum Information    Forum Rules/Guidelines        Forum Rules/Guidelines FAQs    Forum Announcements        Forum Announcements FAQs    Dev Shed Gaming Center        Go to the Dev Shed Battle Arena        Go to the Dev Shed Arcade Games        Go to the Legend of the Green Dragon    Suggestions & Feedback        Suggestions & Feedback FAQs

 Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |