Hi all. This project2 is an extension of a previous project where I chose the 'quick sort' algorithm. I will post the source code I used for that previous project. Here are the requirements for project2.

Project 2 involves an analysis of the results that you obtained in first project. You are to submit a paper, written with Microsoft Word, that discusses the results of your analysis. Grading of the

second

part will be based on the following items:

A brief introduction of the sorting algorithm that you have selected and how the two versions of the algorithm compare

A discussion of the critical operation that you chose to count with an explanation of why you selected it

A Big- analysis of the two versions of the algorithm

A discussion of the results of your study, which should include

o graphs of your results o a comparison of the performance of the two versions of the algorithm o a comparison of the critical operation results and the actual execution time

measurements o a discussion of the significance of the standard deviation results and how it

reflects the data sensitivity of your algorithm o how your results compare to your Big- analysis

A conclusion that summarizes the important observations of your study

If for any reason, it was necessary to revise the program you submitted in project 1, the revised source code should also be included along with the paper.

Here is the source code I used for the previous project:

BENCH MARK SORTS CLASS:

public class BenchmarkSorts {

/**

* fields

*/

int[] sizes;

int runs = 50; // number of iterations of each size

/**

* Statistic of recursive sort = r[Couts/Times], iterative = i[Couts/Times]

* each inner array represent a different size based on int[] size

* inner count array contains 1) average critical count, 2) time std

* inner count array contains 1) average critical count, 2) time std

*/

ArrayList> rCountStats = new ArrayList>();

ArrayList> iCountStats = new ArrayList>();

ArrayList> rTimeStats = new ArrayList>();

ArrayList> iTimeStats = new ArrayList>();

/**

* Constructors

* @param sizes represents the input sizes the algo sorts

*/

public BenchmarkSorts(int[] sizes) {

this.sizes = sizes;

}

/**

* Methods

*/

/**

* Main method executing the benchmarking process

*/

public void runSorts() {

QuickSort qs = new QuickSort();

// run stats for different sizes

for (int i = 0; i < sizes.length; i++) {

// temp arrays collecting results of each run

ArrayList countRecur = new ArrayList();

ArrayList timesRecur = new ArrayList();

ArrayList countIter = new ArrayList();

ArrayList timesIter = new ArrayList();

for (int j = 0; j < runs; j++) {

int[] input = generateRandArr(sizes[i], 100);

// Run recursive sort

qs.recursiveSort(input);

countRecur.add(qs.getCount());

timesRecur.add(qs.getTime());

// Run iterative sort

qs.iterativeSort(input);

countIter.add(qs.getCount());

timesIter.add(qs.getTime());

}

// calculate statistics

rCountStats.add(getCountStats(countRecur));

rTimeStats.add(getTimeStats(timesRecur));

iCountStats.add(getCountStats(countIter));

iTimeStats.add(getTimeStats(timesIter));

}

}

/**

* outputs statistics to .txt file using FileWriter 'writer'

*/

public void displayReport() {

// OUTPUT: .txt

try {

FileWriter writer = new FileWriter("OutputStats.txt", false); // T/F=override contents

BufferedWriter bw = new BufferedWriter(writer);

// write header of file

bw.write("Data Set" + "\t\t\t\t" + "Recursive Quicksort" +

"\t\t\t\t\t\t\t\t" + "Iterative Quicksort");

bw.newLine();

bw.write("Size n");

bw.newLine();

bw.write("\t" + "Average Critical" + "\t" + "Standard" + "\t" +

"Average" + "\t\t" + "Standard" + "\t" +

"Average Critical" + "\t" + "Standard" + "\t" +

"Average" + "\t\t" + "Standard");

bw.newLine();

bw.write("\t" + "Operation Count" + "\t\t" + "Deviation of" + "\t" +

"Execution" + "\t" + "Deviation of" + "\t" +

"Operation Count" + "\t\t" + "Deviation of" + "\t" +

"Execution" + "\t" + "Deviation of");

bw.newLine();

bw.write("\t\t\t\t" + "Count" + "\t\t" + "Time (ns)" +

"\t" + "Time (ns)" +

"\t\t\t\t" + "Count" + "\t\t" + "Time (ns)" +

"\t" + "Time (ns)");

bw.newLine();

// write data

for (int i = 1; i < sizes.length; i++) {

bw.write(sizes[i] + "\t" +

rCountStats.get(i).get(0) + " " + "\t\t" +

rCountStats.get(i).get(1) + "\t\t" +

rTimeStats.get(i).get(0) + " " + "\t" +

rTimeStats.get(i).get(1) + " " + "\t" +

iCountStats.get(i).get(0) + " " + "\t\t" +

iCountStats.get(i).get(1) + "\t\t" +

iTimeStats.get(i).get(0) + " " + "\t" +

iTimeStats.get(i).get(1));

bw.newLine();

}

bw.close();

}

catch (IOException e) {

e.printStackTrace();

}

// OUTPUT: .MD

try {

FileWriter writer = new FileWriter("OutputStats.md", false); // T/F=override contents

BufferedWriter bw = new BufferedWriter(writer);

// write header of file

bw.write("| Data Set Size n | Recursive Quicksort |||| Iterative Quicksort ||||");

bw.newLine();

bw.write("| --- | --- | --- | --- | --- | --- | --- | --- | --- |");

bw.newLine();

bw.write("|| Average Critical Operation Count | " +

"Standard Deviation of Count | " +

"Average Execution Time (ns) | " +

"Standard Deviation of Time (ns) | " +

"Average Critical Operation Count | " +

"Standard Deviation of Count | " +

"Average Execution Time (ns) | " +

"Standard Deviation of Time (ns) |");

bw.newLine();

bw.write("| --- | --- | --- | --- | --- | --- | --- | --- | --- |");

bw.newLine();

// write data

for (int i = 1; i < sizes.length; i++) {

bw.write("|" + sizes[i] + "|" +

rCountStats.get(i).get(0) + "|" +

rCountStats.get(i).get(1) + "|" +

rTimeStats.get(i).get(0) + "|" +

rTimeStats.get(i).get(1) + "|" +

iCountStats.get(i).get(0) + "|" +

iCountStats.get(i).get(1) + "|" +

iTimeStats.get(i).get(0) + "|" +

iTimeStats.get(i).get(1) + "|");

bw.newLine();

}

bw.close();

}

catch (IOException e) {

e.printStackTrace();

}

}

/**

* Generates a random array of ints

* @param n = number of ints to be generated

* @param max = largest value of int to be generated

*/

private int[] generateRandArr(int n, int max) {

int[] arr = new int[n];

for (int i = 0; i < n; i++) {

Random rand = new Random();

arr[i] = rand.nextInt(max);

}

return arr;

}

/**

* Calculates mean and std for ArrayList

*/

public ArrayList getCountStats(ArrayList arr) {

ArrayList output = new ArrayList();

// temp fields for calcs

Integer sum = 0;

Integer mean;

Double diff2 = 0.0;

Double std;

// calc sum

for (int i = 0; i < arr.size(); i++){

sum += arr.get(i);

}

mean = sum / arr.size();

// calc sum

for (int i = 0; i < arr.size(); i++){

diff2 += Math.pow((arr.get(i) - mean), 2);

}

std = Math.pow(diff2 / arr.size(), 0.5);

output.add(mean);

output.add(std.intValue());

return output;

}

/**

* Calculates mean and std for ArrayList

*/

public ArrayList getTimeStats(ArrayList arr) {

ArrayList output = new ArrayList();

// temp fields for calcs

Long sum = 0L;

Long mean;

Double diff2 = 0.0;

Double std;

// calc sum

for (int i = 0; i < arr.size(); i++){

sum += arr.get(i);

}

mean = sum / arr.size();

// calc sum

for (int i = 0; i < arr.size(); i++){

diff2 += Math.pow((arr.get(i) - mean), 2);

}

std = Math.pow(diff2 / arr.size(), 0.5);

output.add(mean.longValue());

output.add(std.longValue());

return output;

}

}

QUICK SORT CLASS:

import java.util.ArrayList;

import java.util.Collections;

public class QuickSort implements SortInterface {

/**

* fields

*/

private int count;

private long time;

/**

* default constructor

*/

public QuickSort() {

}

/**

* @see SortInterface

*/

public int getCount() {

return this.count;

}

/**

* @see SortInterface

*/

public long getTime() {

return this.time;

}

/**

* @see SortInterface

*/

public void recursiveSort(int[] list) throws UnsortedException {

this.time = 0;

this.count = 0;

ArrayList ls = new ArrayList();

for (int i = 0; i < list.length; i++) {

ls.add(list[i]);

}

long startTime = System.nanoTime();

quickRecursive(ls, 0, ls.size() - 1);

long endTime = System.nanoTime();

this.time = endTime - startTime;

// check correctness

check(ls, "recursive");

}

/**

* @see SortInterface

*/

public void iterativeSort(int[] list) throws UnsortedException {

this.time = 0;

this.count = 0;

ArrayList ls = new ArrayList();

for (int i = 0; i < list.length; i++) {

ls.add(list[i]);

}

long startTime = System.nanoTime();

quickIterative(ls, 0, ls.size() - 1);

long endTime = System.nanoTime();

this.time = endTime - startTime;

// check correctness

check(ls, "iterative");

}

/**

* Checks that resulting array is correctly sorted

*/

public void check(ArrayList ls, String sortType) {

for (int i = 0; i < (ls.size() - 1); i++) {

if (ls.get(i) > ls.get(i + 1)) {

throw new UnsortedException("Custom exception: " + sortType +

" sort produced wrong result");

}

}

}

/**

* Source: based on pseudocode from 'Introduction to Algorithms' by Cormen

* @param ls: int to be sorted

* CRITICAL operation is defined as the number of comparisons

*/

private void quickRecursive(ArrayList ls, int left, int right) {

if (left >= right) { count++; // CRITICAL operation

return;

}

else {

int pivot = partition(ls, left, right);

quickRecursive(ls, left, pivot - 1);

quickRecursive(ls, pivot + 1, right);

}

}

/**

* Source: based on pseudocode from 'Introduction to Algorithms' by Cormen

* @param ls: int to be sorted

* CRITICAL operation is defined as the number of comparisons

*/

private void quickIterative(ArrayList ls, int left, int right) {

int[] temp_stack = new int[right - left + 1];

int last = -1;

temp_stack[++last] = left;

temp_stack[++last] = right;

while (last > -1) { count++; // CRITICAL operation

int r = temp_stack[last--];

int l = temp_stack[last--];

int pivot = partition(ls, l, r);

// if elements to the left of pivot, add to temp_stack

if (pivot - 1 > l) { count++; // CRITICAL operation

temp_stack[++last] = l;

temp_stack[++last] = pivot - 1;

}

// if elements to the right of pivot, add to temp_stack

if (pivot + 1 < r) { count++; // CRITICAL operation

temp_stack[++last] = pivot + 1;

temp_stack[++last] = r;

}

}

}

/**

* Implement recursive Quicksort

* @param ls: int to be sorted

*/

private int partition(ArrayList ls, int left, int right) {

int value = ls.get(right);

int i = left - 1;

for (int j = left; j < right; j++) {

if (ls.get(j) <= value) { count++; // CRITICAL operation

i++;

Collections.swap(ls, j, i);

}

}

Collections.swap(ls, i + 1, right);

return i + 1;

}

}

SORT INTERFACE CLASS:

public interface SortInterface {

/**

*

* @param list

* - input array to be sorted

*/

public void recursiveSort(int[] list);

/**

*

* @param list

* - input array to be sorted

*/

public void iterativeSort(int[] list);

/**

*

* @return returns the count of significant operations

*/

public int getCount();

/**

*

* @return returns the time to complete the algo

*/

public long getTime();

}

SORT MAIN CLASS:

/*

* CMSC 451 Project 1

* by Kolby Kauffman

*

*/

public class SortMain {

public static void main(String[] args) {

int[] sizes = new int[21];

sizes[0] = 50000; // warmup

for (int i = 1; i < sizes.length; i++) {

sizes[i] = i * 500;

}

BenchmarkSorts run = new BenchmarkSorts(sizes);

run.runSorts();

run.displayReport();

}

}

UNSORTED EXCEPTION CLASS:

public class UnsortedException extends RuntimeException {

public UnsortedException(String message) {

super(message);

}

public UnsortedException() {

super();

}

}