Answered You can hire a professional tutor to get the answer.
Compare the performance of the two versions of the algorithm import java.Random; import java.GridLayout; import java.FileNotFoundException; import...
import java.util.Random;
import java.awt.GridLayout;
import java.io.FileNotFoundException;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JTable;
/**
* BenchmarkSorts.java
* This is a class designed to test sorting algorithms. This utilizes iterative test
* as well as recursive test.
*/
/**
*
*/
public class BenchmarkSorts {
private final int TESTCASES = 10; // How many test cases are being run
private final int TRIALS = 50; // how many trials in each test case
// arrays for storing testData and result data
private int[] sizes;
private int[][][] testData;
private int[][] iterativeCountResults = new int[this.TESTCASES][this.TRIALS];
private long[][] iterativeTimeResults = new long[this.TESTCASES][this.TRIALS];
private int[][] recursiveCountResults = new int[this.TESTCASES][this.TRIALS];
private long[][] recursiveTimeResults = new long[this.TESTCASES][this.TRIALS];
private Object[][] stats = new Object[this.TESTCASES][9];
// File IO items for storing test results
java.io.File iCountFile, iTimeFile, rCountFile, rTimeFile;
java.io.PrintWriter iCountOutput, iTimeOutput, rCountOutput, rTimeOutput;
// Constructor
public BenchmarkSorts(int[] sizes) {
this.sizes = sizes;
createTestData();
}
// Creates and Array of Random Lists of integers between 0 and 99999 to be sorted
private void createTestData() {
Random randomGenerator = new Random();
this.testData = new int[this.TESTCASES][this.TRIALS][];
// Use the sizes array to get the length for each set of test data
for(int i = 0; i < this.TESTCASES; i++) {
for(int j = 0; j < this.TRIALS; j++) {
testData[i][j] = new int[this.sizes[i]];
// Populate each test Array with some random numbers
for(int k = 0; k < this.sizes[i]; k++) {
testData[i][j][k] = randomGenerator.nextInt(100000);
}
}
}
}
// Run the sorts and store the results in the array structures and files
public void runSorts() throws FileNotFoundException {
// Setup files for writing
this.iCountFile = new java.io.File("iCountFile.dat");
this.iTimeFile = new java.io.File("iTimeFile.dat");
this.rCountFile = new java.io.File("rCountFile.dat");
this.rTimeFile = new java.io.File("rTimeFile.dat");
this.iCountOutput = new java.io.PrintWriter(this.iCountFile);
this.iTimeOutput = new java.io.PrintWriter(this.iTimeFile);
this.rCountOutput = new java.io.PrintWriter(this.rCountFile);
this.rTimeOutput = new java.io.PrintWriter(this.rTimeFile);
System.out.print("Starting Tests");
// Loop through each of the testCases and benchmark the sorts
for(int i = 0; i < this.TESTCASES; i++) {
System.out.println("nSorting Lists of size " + this.sizes[i] + ".");
// Repeat the sort for this.TRIALS many times
for(int j = 0; j < this.TRIALS; j++) {
SortInterface sort = new RadixSort();
// Clone the list we are sorting from the testData
int[] list = (int[])testData[i][j].clone();
// Iteratively sort the list
sort.iterativeSort(list);
// Store the Results in the results array
this.iterativeCountResults[i][j] = sort.getCount();
this.iterativeTimeResults[i][j] = sort.getTime();
// Write the results to the output files
this.iCountOutput.print(sort.getCount() + " ");
this.iTimeOutput.print(sort.getTime() + " ");
// Verify that the iterativeSort was successful
try {
verifySorted(list);
} catch (UnsortedException e) {
e.printStackTrace();
}
sort = new RadixSort();
// Clone the list we are sorting from the testData
list = (int[])testData[i][j].clone();
// Recursively sort the list
sort.recursiveSort(list);
// Store the results in the results array
this.recursiveCountResults[i][j] = sort.getCount();
this.recursiveTimeResults[i][j] = sort.getTime();
// Write the results to the output files
this.rCountOutput.print(sort.getCount() + " ");
this.rTimeOutput.print(sort.getTime() + " ");
// Verify that the recursiveSort was successful
try {
verifySorted(list);
} catch (UnsortedException e) {
e.printStackTrace();
}
// print a dot after each trial to show progress in the console window
System.out.print("*");
}
//Print new lines to each file for the next row of data
this.iCountOutput.print("n");
this.iTimeOutput.print("n");
this.rCountOutput.print("n");
this.rTimeOutput.print("n");
}
System.out.println("nTests Complete.");
// Close the files
this.iCountOutput.close();
this.iTimeOutput.close();
this.rCountOutput.close();
this.rTimeOutput.close();
}
// Display the results of the tests in a JTable
public void displayReport() {
// Calculate the stats from the result data to be displayed
calculateStats();
String[] columnNames1 ={"Data Set Size n", "Iterative", "Recursive"};
String[] columnNames = {"Data Set Size n", "Iterative Average Critical Operation Count", "Iterative Standard Deviation of Count",
"Iterative Average Execution Time (ms)", "Iterative Standard Deviation of Time", "Recursive Average Critical Operation Count",
"Recursive Standard Deviation of Count", "Recursive Average Execution Time (ms)", "Recursive Standard Deviation of Time(ms)"
};
JPanel jpanel = new JPanel(new GridLayout(1,0));
final JTable table = new JTable(this.stats,columnNames);
JScrollPane scrollpane = new JScrollPane(table);
table.setFillsViewportHeight(true);
jpanel.add(scrollpane);
jpanel.setOpaque(true);
JFrame frame = new JFrame("Test Results");
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setContentPane(jpanel);
frame.pack();
frame.setVisible(true);
}
/* Run through the supplied list and make sure it is sorted. Throw an unsorted
* exception if not. */
private void verifySorted(int[] list) throws UnsortedException {
for(int i = 0; i < list.length - 1; i++) {
if(list[i] > list[i+1]) {
String errorMsg = "nElements not Sorted Correctly.n"
+ list[i] + " is not less than " + list[i+1] +".n";
throw new UnsortedException(errorMsg);
}
}
}
// Calculate the mean of a list
private double mean(final int list[]) {
double mean = 0.0;
for(int i = 0; i < list.length; i++) {
mean += list[i];
}
return mean / list.length;
}
// Calculate the mean of a list
private double mean(final long list[]) {
double mean = 0.0;
for(int i = 0; i < list.length; i++) {
mean += list[i];
}
return mean / list.length;
}
// Calculate the standardDeviation of a list
private double standardDeviation(final int list[], final double mean) {
double sum = 0.0;
for(int i = 0; i < list.length; i++) {
sum += Math.pow((list[i] - mean), 2);
}
sum = sum / list.length;
return Math.sqrt(sum);
}
// Calculate the standardDeviation of a list
private double standardDeviation(final long list[], final double mean) {
double sum = 0.0;
for(int i = 0; i < list.length; i++) {
sum += Math.pow((list[i] - mean), 2);
}
sum = sum / list.length;
return Math.sqrt(sum);
}
/* Run through each of the results arrays and calculate the stats for each trial.
* Store the results in the stats array. Convert time to milliseconds */
private void calculateStats() {
for(int i = 0; i < this.TESTCASES; i++) {
// Test Cases
this.stats[i][0] = this.sizes[i];
// Iterative Results
this.stats[i][1] = mean(this.iterativeCountResults[i]);
this.stats[i][2] = standardDeviation(this.iterativeCountResults[i], (double)this.stats[i][1]);
this.stats[i][3] = mean(this.iterativeTimeResults[i]) / 100000;
this.stats[i][4] = standardDeviation(this.iterativeTimeResults[i], mean(this.iterativeTimeResults[i])) / 100000;
// Recursive Results
this.stats[i][5] = mean(this.recursiveCountResults[i]);
this.stats[i][6] = standardDeviation(this.recursiveCountResults[i], (double)this.stats[i][5]);
this.stats[i][7] = mean(this.recursiveTimeResults[i]) / 100000;
this.stats[i][8] = standardDeviation(this.recursiveTimeResults[i], mean(this.recursiveTimeResults[i])) / 100000;
}
}
}
import java.util.ArrayList;
/**
* RadixSort.java
*
* A class for implementing a RadixSort both iteratively, and recursively.
* Implements the SortInterface so it can be called by the benchmarkSorts class.
*
* Designed to be used on integer values between 0 and 99999. Was modeled to be
* able to sort zip codes.
*/
/**
*
*/
public class RadixSort implements SortInterface {
// Bins for holding sorted binary values
private ArrayList<Integer> bin0 = new ArrayList<Integer>();
private ArrayList<Integer> bin1 = new ArrayList<Integer>();
// Count the number of times we go through the sorting loop
private int count = 0;
// Used to determine how long a sort took
private long startTime, stopTime;
/* Implement the recursiveSort methods from the SortInterface. Calls a helper
* recursiveSort function after the first pass. Sort from Most Significant Digit
* to Least Significant Digit.
*
*/
public int[] recursiveSort(int[] list) {
// Start the clock
this.startTime = System.nanoTime();
// MSB sort, so starting with a high mask and working down to 0
int mask = 65536;
// Run the first pass before calling recursively also increment count
for(int i = 0; i < list.length; i++) {
count++;
/* Use the mask to look at each digit, if we get a 1 send the number to the
bin1 ArrayList, otherwise send it to bin0. */
if((mask & list[i]) == mask) {
bin1.add(list[i]);
} else {
bin0.add(list[i]);
}
}
// Call recursively on each bin
recursiveSort(bin0, mask);
recursiveSort(bin1, mask);
// Copy and combine the bins back to the list
for(int k = 0; k < list.length; k++) {
if(!bin0.isEmpty()) {
list[k] = bin0.remove(0);
} else {
list[k] = bin1.remove(0);
}
}
// Stop the clock
this.stopTime = System.nanoTime();
return list;
}
private ArrayList<Integer> recursiveSort(ArrayList<Integer> list, int mask) {
// Create local_bins for holding the sorted values
ArrayList<Integer> local_bin0 = new ArrayList<Integer>();
ArrayList<Integer> local_bin1 = new ArrayList<Integer>();
// Base case, we have gone through each bit
if(mask <= 0) {
return list;
}
// Advance and look at the next Least Significant bit
mask = mask >> 1;
// Run another sorting pass before calling recursively again
// This is where we increment count
for(int i = 0; i < list.size(); i++) {
count++;
/* Use the mask to look at each digit, if we get a 1 send the number to the
bin1 ArrayList, otherwise send it to bin0. */
if((mask & list.get(i)) == mask) {
local_bin1.add(list.get(i));
} else {
local_bin0.add(list.get(i));
}
}
// Call recursively on each bin
recursiveSort(local_bin0, mask);
recursiveSort(local_bin1, mask);
// Copy and combine the bins back to the list
for(int k = 0; k < list.size(); k++) {
if(!local_bin0.isEmpty()) {
list.set(k, local_bin0.remove(0));
} else {
list.set(k, local_bin1.remove(0));
}
}
return list;
}
/* Implements the interetiveSort method from the SortInterface. Uses a mask
* to look at each bit and sort it into the correct bin before recombining into
* a single list.
*/
@Override
public int[] iterativeSort(int[] list) {
// Start the clock
this.startTime = System.nanoTime();
int mask = 1;
// Use a mask to iterate over each bit that we are looking at
for(int i = 0; i < 17; i++) {
// Increment the Mask each time we run through the for loop
if(i != 0) {
mask = mask << 1;
}
// Iterate over each element of the list
// This is where we update count to reflect that we are looking at each
// list element again
for(int j = 0; j < list.length; j++) {
count++; // increment the count for each element visited
// Use the mask to select the correct bin
if((mask & list[j]) == mask) {
bin1.add(list[j]);
} else {
bin0.add(list[j]);
}
}
// Copy the bins back to the list
for(int k = 0; k < list.length; k++) {
if(!bin0.isEmpty()) {
list[k] = bin0.remove(0);
} else {
list[k] = bin1.remove(0);
}
}
}
// Stop the clock
this.stopTime = System.nanoTime();
return list;
}
@Override
public int getCount() {
return count;
}
@Override
public long getTime() {
return this.stopTime - this.startTime;
}
}
public interface SortInterface {
public int[] recursiveSort(int[] list);
public int[] iterativeSort(int[] list);
public int getCount();
public long getTime();
}
import java.io.FileNotFoundException;
/**
* SortMain.java
*
* Driver program that calls and runs the BenchmarkSorts methods. Program
* is used to test the effectiveness of a Radix Sort in this case.
*/
/**
*
*/
public class SortMain {
public static void main(String[] args) {
// Test Data set sizes to be used by the benchmark tools
int[] sizes = {50, 100, 200, 400, 800,1600,1600,3200,6400,12800};
BenchmarkSorts benchmark = new BenchmarkSorts(sizes);
// Run the sorts
try {
benchmark.runSorts();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
// Display the benchmark report
benchmark.displayReport();
}
}
/**
* UnsortedException.java
*
* Simple exception class used by the benchmarkSorts class. Is thrown when a list
* is unexpectedly unsorted.
*/
/**
*
*/
public class UnsortedException extends Exception {
private static final long serialVersionUID = 1L;
public UnsortedException(String msg) {
super(msg);
}
}
// Recursive approach of the Quick Sort
import java.util.ArrayList;
import java.util.Iterator;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class QuickSort {
private static void swap(int[] a1, int in, int jn) {
int temp = a1[in];
a1[in] = a1[jn];
a1[jn] = temp;
}
private static void Quicksort(int liste[], int from, int to) {
if (from >= to) {
return;
}
int pvot = liste[from];
int in = from - 1;
int jn = to + 1;
while (in < jn) {
in++;
while (liste[in] < pvot) { in++; }
jn--;
while (liste[jn] > pvot) { jn--; }
if (in < jn) {
swap(liste, in, jn);
}
}
Quicksort(liste, from, jn);
Quicksort(liste, jn + 1, to);
}
public static int[] Quicksort(int [] liste) {
Quicksort(liste, 0, liste.length-1);
return liste;
}
public static void main(String args[]) throws Exception
{
String liste="";
int in=0,n=0;
QuickSort s= new QuickSort();
ArrayList<Integer> arrlist=new ArrayList<Integer>();
System.out.println(" ");
System.out.println(" ");
System.out.println("Enter the list for sorting and hit enter for each item");
System.out.println("Write 'complete' when done and hit 'enter'.");
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
while(!(liste=bf.readLine()).equalsIgnoreCase("complete")){
int intelement=Integer.parseInt(liste);
arrlist.add(intelement);
}
int elementlist[] = new int[arrlist.size()];
Iterator<Integer> iter = arrlist.iterator();
for (int jn=0;iter.hasNext();jn++) {
elementlist[jn] = iter.next();
}
elementlist=Quicksort(elementlist);
System.out.println("Recursive approach of Quicksort: ");
for (int jn=0;jn<elementlist.length;jn++) {
System.out.println(elementlist[jn]+" ");
}
}
}
