Hi All,
I have a new assignment which I have worked most of the way out, except I have one issue. When I sort the large text file it does not print out all the information at that moment, I have to hit enter a couple of times before all the infroamtion comes out, not like it does for the small text file? Thanks in Advance!!
Situation:
Large file?
yes
Merge sort done!
MergeSort calls: 59999
Merge Calls: 29999
Time Elapsed: 701 Milliseconds
Selection sort took 449985000 iterations.
Time Elapsed: 8892 Milliseconds
versus
Large file?
no
Merge sort done!
MergeSort calls: 1999
Merge Calls: 999
Time Elapsed: 851 Milliseconds
Selection sort took 499500 iterations.
Time Elapsed: 20 Milliseconds
Here is the assignment:
For this lab, implement selection sort and merge sort. Add counters to the methods to track the number of comparisons and assignments that occur in each algorithm.
Implement a metric that allows you to calculate the running time of the algorithms. HINT: java.util provides time, timer and timestamp classes.
Sort the Small.txt and Large.txt files and write a brief comparison of the algorithms you implemented.
Here is the code:
import java.util.ArrayList;
public class Sort
{
int i;
int j;
//make arraylist
ArrayList<Integer> a = new ArrayList();
// count how many iterations are performed during the sort
private long iterations = 0;
public ArrayList<Integer> selectionSort(ArrayList<Integer> a)
{
//checks every other number and gives one the name i and 1 j
for (int i=0; i < a.size()-1; i++)
{
for (int j=i+1; j < a.size(); j++)
{
//check to see which is greater to put them in order
if (a.get(i) > a.get(j))
{
//If x is the greater element, exchange elements
int temp = a.get(i);
a.add(i,a.get(j));
a.add(j,temp);
//iterations++;
}
iterations++;
}
}
System.out.println("Selection sort took " + iterations + " iterations.");
//return list
return a;
}
}
import java.util.ArrayList;
public class Sorter
{
//declare as integers
private int mergesort = 0;
private int merge = 0;
public ArrayList Sort(ArrayList<Integer> a)
{
//just make sure they're all zero\
//uses method from bottom
while(!leastToGreatest(a))
{
for(int x = 0; x < a.size() - 1; x++)
{
if (a.get(x) > a.get(x+1))
//use change method below and sort
a = change(a, x);
}
}
return a;
}
// make a temporary instance and make instances of positions
private ArrayList change(ArrayList<Integer> a, int position)
{
int temp = a.get(position);
a.set(position, a.get(position+1));
a.set(position+1, temp);
return a;
}
private boolean leastToGreatest(ArrayList<Integer> a)
{
for(int x = 1; x < a.size(); x++)
{
//put ArrayList in order using this loop
if(a.get(x) < a.get(x-1))
return false;
}
return true;
}
// make array to hold positions
public int[] getData()
{
return new int[] {mergesort, merge};
}
//LAB
public ArrayList<Integer> MergeSort(ArrayList<Integer> a)
{
mergesort++;
// make 3 lists to make merging easier
ArrayList<Integer> result = new ArrayList<Integer>();
ArrayList<Integer> left = new ArrayList<Integer>();
ArrayList<Integer> right = new ArrayList<Integer>();
//already sorted in this case
if(a.size() <= 1)
return a;
else
{
//perform these loops if arraylist is unsorted
int half = a.size() / 2;
for (int x = 0; x < half; x++)
{
left.add(a.get(x));
}
for (int x = half; x < a.size(); x++)
{
right.add(a.get(x));
}
left = MergeSort(left);
right = MergeSort(right);
result = Merge(left, right);
return result;
}
}
private ArrayList<Integer> Merge(ArrayList<Integer> left, ArrayList<Integer> right)
{
//merge method used to complete sorting
merge++;
ArrayList<Integer> result = new ArrayList<Integer>();
//has to be greater than 0 otherwise no merging is needed
while(left.size() > 0 && right.size() > 0)
{
//put the lower numbers on the left
if (left.get(0) <= right.get(0))
{
result.add(left.get(0));
left.remove(0);
}
else
{
result.add(right.get(0));
right.remove(0);
}
}
//put the higher numbers on the right
if ( left.size() > right.size())
result.addAll(left);
else if (left.size() <= right.size())
result.addAll(right);
return result;
}
}
import java.util.*;
import java.io.*;
public class test
{
// main
public static void main(String[] args)
{
// make longs for timestamps
long begin, end;
//import scanner for user input
Scanner userinput = new Scanner(System.in);
System.out.println("Large file?");
String input = userinput.nextLine();
String first = "";
String outputFile = "";
String outputFile2 = "";
//create if statement to determine whether user wants a small text file or a large one
if(input.equalsIgnoreCase("yes"))
{
// read in file
first = "H:\\Computer Science 160\\Lab 9\\Large.txt";
outputFile = "H:\\largeSorted.txt";
outputFile2 = "H:\\largeSelectionSort.txt";
}
else if (input.equalsIgnoreCase("no"))
{
//read in file
first = "H:\\Computer Science 160\\Lab 9\\small.txt";
outputFile = "H:\\smallSorted.txt";
outputFile2 = "H:\\smallSelectionSort.txt";
}
try
{
//apply sorting method
Scanner scn = new Scanner(new File(first));
Sorter s = new Sorter();
Sort sort = new Sort();
//use arraylist
ArrayList<Integer> p = new ArrayList();
while (scn.hasNext())
{
p.add(scn.nextInt());
}
//INSERT TIME CALCULATION STUFF
begin = System.currentTimeMillis();
p = s.MergeSort(p);
end = System.currentTimeMillis();
//print back the output placed in the new file
PrintWriter output = new PrintWriter(new FileWriter(outputFile));
// get the entire size
for(int x = 0; x < p.size(); x++)
output.println(p.get(x));
System.out.println("Merge sort done!");
System.out.println("MergeSort calls: " + s.getData()[0] + "\nMerge Calls: " + s.getData()[1]);
System.out.println("Time Elapsed: " + (end - begin) + " Milliseconds");
output.close();
begin = System.currentTimeMillis();
p = sort.selectionSort(p);
end = System.currentTimeMillis();
//print out the second sort for merge
PrintWriter output2 = new PrintWriter(new FileWriter(outputFile2));
for(int x = 0; x < p.size(); x++)
output2.println(p.get(x));
System.out.println("Time Elapsed: " + (end - begin) + " Milliseconds");
output2.close();
}
//catch a general exception for ease
catch (Exception e)
{
System.out.println(e);
}
}
}