I am working on a project right now in which I am making a java project that can import a list of people from a csv file, and order them by first name, last name, and their birth year using different sorting algorithms. I have written the code for the selection sort, merge sort, and quick sort algorithms, and tried to use the comparator interface to allow them to be used with the strings of the first and last names and also the integer value of the birth years.
The people and their attributes are in a csv file in this fashion for over 18,000 people:
nameLast nameFirst birthYear
De Los Santos Valerio 1972
Tekulve Kent 1947
Valentine Fred 1935
I want the program to read this csv file, and assign these values into an array of the class Human, which can hold 2 strings (firstName and lastName) and a an integer (birthYear). Then, I want the program to use the sorting algorithms that I have implemented to sort by lastName, and then again by firstName. Then, I want to sort them by birthYear, in ascending order, and also descending order. I want to just output these so that I can copy them into a word document, just to see that the program worked; for this part, I guess it doesn't really matter which algorithm is used.
Then next part is trickier for me. I want to measure the time it takes each of the three algorithms to sort by different criteria, and with different starting orderliness to the array. For example:
- by lastName, array starts out in random order
- by lastName, array is already sorted
- by lastName, array is sorted in the wrong order (ascending instead of descending, for example)
- by birthYear, array starts out in random order
- by birthYear, array is already sorted
- by birthYear, array is already sorted in the wrong order
In order to do this, will I have to create separate csv files with the preset order type, or is there a way just to manipulate the order of the human array from within java? I already have experience using a stopwatch function to measure how long it will take for each sort to execute, but I am not sure how to proceed. Here is my code so far. I am gettting a lot of error messages, but I think the source of the problems lies in my lack of general knowledge of Java syntax and protocol. I have created the sort algorithms and the human class, but I am not sure how to go about with the rest. If someone could teach me what I did wrong and how I can implement the csv file, I would be very thankful.
package project_1_sorting;
import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Arrays;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Locale;
public class Project1 {
public class Selection_Sort {
private Object[] a;
private int i;
private int j;
{ Object t = a[i]; a[i] = a[j]; a[j] = t; }
public static void sort(Object[] a, Comparator comparator)
{
int N = a.length;
for (int i = 0; i < N; i++)
{
int min = i;
for (int j = i+1; j < N; j++)
if (less(comparator, a[j] , a[min])) min = j;
exch(a,i,min);
}
}
private static boolean less (Comparator c, Object v, Object w)
{
return c.compare(v,w) < 0;
}
private static void exch (Object[] a, int i, int j)
{
Object swap = a[i]; a[i] = a[j]; a[j] = swap;
}
}
public class Merge_Sort {
public static void merge(Object[] a, Comparator comparator, int lo, int mid, int hi)
{ // Merge a[lo..mid] with a[mid+1..hi].
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) // Copy a[lo..hi] to aux[lo..hi].
aux[k] = a[k];
for (int k = lo; k <= hi; k++) // Merge back to a[lo..hi].
if (i > mid) a[k] = aux[j++];
else if (j > hi ) a[k] = aux[i++];
else if (less(comparator,aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
private static Object[] aux;
public static void sort(Object[] a, Comparator comparator);
{
aux = new Object[a.length];
sort(comparator,a, 0, a.length - 1);
}
private static void sort (Object[] a, int lo, int hi, Comparator comparator)
{// Sort a[lo...hi].
if (hi <= lo) return;
int mid = lo + (hi - lo)/2;
sort(Comparator,a, lo, mid);
sort(Comparator,a, mid+1, hi);
merge(Comparator,a, lo, mid, hi);
}
private static boolean less (Comparator c, Object v, Object w)
{
return c.compare(v,w) < 0;
}
private static void exch (Object[] a, int i, int j)
{
Object swap = a[i]; a[i] = a[j]; a[j] = swap;
}
}
public class Quick_Sort {
public class Quick
{
public static void sort(Object[] a)
{
StdRandom.shuffle(a); // Eliminate dependence on input.
sort(a, 0, a.length - 1);
}
private static void sort(Object[] a, int lo, int hi, Comparator comparator)
{
if (hi <= lo) return;
int j = partition(a, lo, hi); // Partition (see page 291).
sort(comparator,a, lo, j-1); // Sort left part a[lo .. j-1].
sort(comparator,a, j+1, hi); // Sort right part a[j+1 .. hi].
}
private static int partition(Object[] a, int lo, int hi, Comparator comparator)
{ // Partition into a[lo..i-1], a[i], a[i+1..hi].
int i = lo, j = hi+1; // left and right scan indices
Object v = a[lo]; // partitioning item
while (true)
{ // Scan right, scan left, check for scan complete, and exchange.
while (less(comparator,a[++i], v)) if (i == hi) break;
while (less(comparator,v, a[--j])) if (j == lo) break;
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j); // Put v = a[j] into position
return j; // with a[lo..j-1] <= a[j] <= a[j+1..hi].
}
}
private static void swap(int[] a, int i, int j) {
// TODO Auto-generated method stub
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static boolean less (Comparator c, Object v, Object w)
{
return c.compare(v,w) < 0;
}
private static void exch (Object[] a, int i, int j)
{
Object swap = a[i]; a[i] = a[j]; a[j] = swap;
}
}
public class Human ()
{
String firstName;
String lastName;
int birthYear;
}
}
here is my second file
package project_1_sorting;
/*************************************************************************
* Compilation: javac StdOut.java
* Execution: java StdOut
*
* Writes data of various types to standard output.
*
*************************************************************************/
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Locale;
public final class StdOut {
// force Unicode UTF-8 encoding; otherwise it's system dependent
private static final String CHARSET_NAME = "UTF-8";
// assume language = English, country = US for consistency with StdIn
private static final Locale LOCALE = Locale.US;
// send output here
private static PrintWriter out;
// this is called before invoking any methods
static {
try {
out = new PrintWriter(new OutputStreamWriter(System.out, CHARSET_NAME), 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(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);
}
}
And here is my third file
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package project_1_sorting;
import java.util.Random;
public final class StdRandom {
private static Random random; // pseudo-random number generator
private static long seed; // pseudo-random number generator seed
// static initializer
static {
// this is how the seed was set in Java 1.4
seed = System.currentTimeMillis();
random = new Random(seed);
}
// don't instantiate
private StdRandom() { }
/**
* Sets the seed of the psedurandom number generator.
*/
public static void setSeed(long s) {
seed = s;
random = new Random(seed);
}
/**
* Returns the seed of the psedurandom number generator.
*/
public static long getSeed() {
return seed;
}
/**
* Return real number uniformly in [0, 1).
*/
public static double uniform() {
return random.nextDouble();
}
/**
* Returns an integer uniformly between 0 (inclusive) and N (exclusive).
* @throws IllegalArgumentException if <tt>N <= 0</tt>
*/
public static int uniform(int N) {
if (N <= 0) throw new IllegalArgumentException("Parameter N must be positive");
return random.nextInt(N);
}
///////////////////////////////////////////////////////////////////////////
// STATIC METHODS BELOW RELY ON JAVA.UTIL.RANDOM ONLY INDIRECTLY VIA
// THE STATIC METHODS ABOVE.
///////////////////////////////////////////////////////////////////////////
/**
* Returns a real number uniformly in [0, 1).
* @deprecated clearer to use {@link #uniform()}
*/
public static double random() {
return uniform();
}
/**
* Returns an integer uniformly in [a, b).
* @throws IllegalArgumentException if <tt>b <= a</tt>
* @throws IllegalArgumentException if <tt>b - a >= Integer.MAX_VALUE</tt>
*/
public static int uniform(int a, int b) {
if (b <= a) throw new IllegalArgumentException("Invalid range");
if ((long) b - a >= Integer.MAX_VALUE) throw new IllegalArgumentException("Invalid range");
return a + uniform(b - a);
}
/**
* Returns a real number uniformly in [a, b).
* @throws IllegalArgumentException unless <tt>a < b</tt>
*/
public static double uniform(double a, double b) {
if (!(a < b)) throw new IllegalArgumentException("Invalid range");
return a + uniform() * (b-a);
}
/**
* Returns a boolean, which is true with probability p, and false otherwise.
* @throws IllegalArgumentException unless <tt>p >= 0.0</tt> and <tt>p <= 1.0</tt>
*/
public static boolean bernoulli(double p) {
if (!(p >= 0.0 && p <= 1.0))
throw new IllegalArgumentException("Probability must be between 0.0 and 1.0");
return uniform() < p;
}
/**
* Returns a boolean, which is true with probability .5, and false otherwise.
*/
public static boolean bernoulli() {
return bernoulli(0.5);
}
/**
* Returns a real number with a standard Gaussian distribution.
*/
public static double gaussian() {
// use the polar form of the Box-Muller transform
double r, x, y;
do {
x = uniform(-1.0, 1.0);
y = uniform(-1.0, 1.0);
r = x*x + y*y;
} while (r >= 1 || r == 0);
return x * Math.sqrt(-2 * Math.log(r) / r);
// Remark: y * Math.sqrt(-2 * Math.log(r) / r)
// is an independent random gaussian
}
/**
* Returns a real number from a gaussian distribution with given mean and stddev
*/
public static double gaussian(double mean, double stddev) {
return mean + stddev * gaussian();
}
/**
* Returns an integer with a geometric distribution with mean 1/p.
* @throws IllegalArgumentException unless <tt>p >= 0.0</tt> and <tt>p <= 1.0</tt>
*/
public static int geometric(double p) {
if (!(p >= 0.0 && p <= 1.0))
throw new IllegalArgumentException("Probability must be between 0.0 and 1.0");
// using algorithm given by Knuth
return (int) Math.ceil(Math.log(uniform()) / Math.log(1.0 - p));
}
/**
* Return an integer with a Poisson distribution with mean lambda.
* @throws IllegalArgumentException unless <tt>lambda > 0.0</tt> and not infinite
*/
public static int poisson(double lambda) {
if (!(lambda > 0.0))
throw new IllegalArgumentException("Parameter lambda must be positive");
if (Double.isInfinite(lambda))
throw new IllegalArgumentException("Parameter lambda must not be infinite");
// using algorithm given by Knuth
// see http://en.wikipedia.org/wiki/Poisson_distribution
int k = 0;
double p = 1.0;
double L = Math.exp(-lambda);
do {
k++;
p *= uniform();
} while (p >= L);
return k-1;
}
/**
* Returns a real number with a Pareto distribution with parameter alpha.
* @throws IllegalArgumentException unless <tt>alpha > 0.0</tt>
*/
public static double pareto(double alpha) {
if (!(alpha > 0.0))
throw new IllegalArgumentException("Shape parameter alpha must be positive");
return Math.pow(1 - uniform(), -1.0/alpha) - 1.0;
}
/**
* Returns a real number with a Cauchy distribution.
*/
public static double cauchy() {
return Math.tan(Math.PI * (uniform() - 0.5));
}
/**
* Returns a number from a discrete distribution: i with probability a[i].
* throws IllegalArgumentException if sum of array entries is not (very nearly) equal to <tt>1.0</tt>
* throws IllegalArgumentException unless <tt>a[i] >= 0.0</tt> for each index <tt>i</tt>
*/
public static int discrete(double[] a) {
double EPSILON = 1E-14;
double sum = 0.0;
for (int i = 0; i < a.length; i++) {
if (!(a[i] >= 0.0)) throw new IllegalArgumentException("array entry " + i + " must be nonnegative: " + a[i]);
sum = sum + a[i];
}
if (sum > 1.0 + EPSILON || sum < 1.0 - EPSILON)
throw new IllegalArgumentException("sum of array entries does not approximately equal 1.0: " + sum);
// the for loop may not return a value when both r is (nearly) 1.0 and when the
// cumulative sum is less than 1.0 (as a result of floating-point roundoff error)
while (true) {
double r = uniform();
sum = 0.0;
for (int i = 0; i < a.length; i++) {
sum = sum + a[i];
if (sum > r) return i;
}
}
}
/**
* Returns a real number from an exponential distribution with rate lambda.
* @throws IllegalArgumentException unless <tt>lambda > 0.0</tt>
*/
public static double exp(double lambda) {
if (!(lambda > 0.0))
throw new IllegalArgumentException("Rate lambda must be positive");
return -Math.log(1 - uniform()) / lambda;
}
/**
* Rearrange the elements of an array in random order.
*/
public static void shuffle(Object[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int r = i + uniform(N-i); // between i and N-1
Object temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
/**
* Rearrange the elements of a double array in random order.
*/
public static void shuffle(double[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int r = i + uniform(N-i); // between i and N-1
double temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
/**
* Rearrange the elements of an int array in random order.
*/
public static void shuffle(int[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int r = i + uniform(N-i); // between i and N-1
int temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
/**
* Rearrange the elements of the subarray a[lo..hi] in random order.
*/
public static void shuffle(Object[] a, int lo, int hi) {
if (lo < 0 || lo > hi || hi >= a.length) {
throw new IndexOutOfBoundsException("Illegal subarray range");
}
for (int i = lo; i <= hi; i++) {
int r = i + uniform(hi-i+1); // between i and hi
Object temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
/**
* Rearrange the elements of the subarray a[lo..hi] in random order.
*/
public static void shuffle(double[] a, int lo, int hi) {
if (lo < 0 || lo > hi || hi >= a.length) {
throw new IndexOutOfBoundsException("Illegal subarray range");
}
for (int i = lo; i <= hi; i++) {
int r = i + uniform(hi-i+1); // between i and hi
double temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
/**
* Rearrange the elements of the subarray a[lo..hi] in random order.
*/
public static void shuffle(int[] a, int lo, int hi) {
if (lo < 0 || lo > hi || hi >= a.length) {
throw new IndexOutOfBoundsException("Illegal subarray range");
}
for (int i = lo; i <= hi; i++) {
int r = i + uniform(hi-i+1); // between i and hi
int temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
/**
* Unit test.
*/
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
if (args.length == 2) StdRandom.setSeed(Long.parseLong(args[1]));
double[] t = { .5, .3, .1, .1 };
StdOut.println("seed = " + StdRandom.getSeed());
for (int i = 0; i < N; i++) {
StdOut.printf("%2d " , uniform(100));
StdOut.printf("%8.5f ", uniform(10.0, 99.0));
StdOut.printf("%5b " , bernoulli(.5));
StdOut.printf("%7.5f ", gaussian(9.0, .2));
StdOut.printf("%2d " , discrete(t));
StdOut.println();
}
String[] a = "A B C D E F G".split(" ");
for (String s : a)
StdOut.print(s + " ");
StdOut.println();
}
}
