Hi all. This project2 is an extension of a previous project where I chose the \'
ID: 3857158 • Letter: H
Question
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<ArrayList<Integer>> rCountStats = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> iCountStats = new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Long>> rTimeStats = new ArrayList<ArrayList<Long>>();
ArrayList<ArrayList<Long>> iTimeStats = new ArrayList<ArrayList<Long>>();
/**
* 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<Integer> countRecur = new ArrayList<Integer>();
ArrayList<Long> timesRecur = new ArrayList<Long>();
ArrayList<Integer> countIter = new ArrayList<Integer>();
ArrayList<Long> timesIter = new ArrayList<Long>();
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" + " " + "Recursive Quicksort" +
" " + "Iterative Quicksort");
bw.newLine();
bw.write("Size n");
bw.newLine();
bw.write(" " + "Average Critical" + " " + "Standard" + " " +
"Average" + " " + "Standard" + " " +
"Average Critical" + " " + "Standard" + " " +
"Average" + " " + "Standard");
bw.newLine();
bw.write(" " + "Operation Count" + " " + "Deviation of" + " " +
"Execution" + " " + "Deviation of" + " " +
"Operation Count" + " " + "Deviation of" + " " +
"Execution" + " " + "Deviation of");
bw.newLine();
bw.write(" " + "Count" + " " + "Time (ns)" +
" " + "Time (ns)" +
" " + "Count" + " " + "Time (ns)" +
" " + "Time (ns)");
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();
}
// 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<Integer>
*/
public ArrayList<Integer> getCountStats(ArrayList<Integer> arr) {
ArrayList<Integer> output = new ArrayList<Integer>();
// 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<Long>
*/
public ArrayList<Long> getTimeStats(ArrayList<Long> arr) {
ArrayList<Long> output = new ArrayList<Long>();
// 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<Integer> ls = new ArrayList<Integer>();
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<Integer> ls = new ArrayList<Integer>();
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<Integer> 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<Integer> 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<Integer> 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<Integer> 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();
}
}
Explanation / Answer
Sorting is the process of converting a set of values into a sequence of values ordered by a binary relation.
Selection Sort.
Selection sort takes as input a set (or multiset) of values, and produces a list of values as its output, where the list contains the same values as the original set, but ordered according to the given ordering relation.
Iterative Version:
public int[] iterativeSort(int[] list) {
startTime = System.currentTimeMillis();
int i, j, minIndex;
int temp;
for (i = 0; i < list.length - 1; i++) {
minIndex = i;
for (j = i + 1; j < list.length; j++) {
if (list[minIndex] > (list[j]))
minIndex = j;
count++;
}
// swap items
if (minIndex != i) {
temp = list[minIndex];
list[minIndex] = list[i];
list[i] = temp;
}
}
endTime = System.currentTimeMillis();
return list;
}
Recursive Version:
public int[] rescursiveSort(int[] list, int n) {
count++;
if (n == list.length - 1) {
return list;
}
int temp, minIndex = n;
for (int i = n + 1; i < list.length; i++) {
if (list[i] < list[minIndex]) {
minIndex = i;
}
}
temp = list[n];
list[n] = list[minIndex];
list[minIndex] = temp;
return rescursiveSort(list, n + 1);
}
Selection sort is also known as in-place sort meaning it requires no space other than that required by the input data in our case is the list and a few variables whose number does not depend on the size of the set being sorted.
Thus its asymptotic space complexity is Q(n).
Selection sort is algorithm in which average case and worst case costs are the same. If we calculate the number of comparisons made, the ith iteration requires that we find the minimum of b[i...n] which requires n-i comparisons.
Hence the total number of comparisons is
(n) + (n-1) + (n-2) + ...+ 3 + 2 + 1 + 0 = n(n+1)/2
The swap operation requires 3 assignments for the program, the number of assignments of array entries is (always) 3n. Thus, measured by comparisons or assignments operations or both together, the asymptotic time complexity of selection sort is Q(n2).
We can also analyze the complexity of selection sort by writing a recurrence system from the recursive form of the algorithm. If T(n) denotes the number of comparisons required to sort a set of n elements, the following recurrence equations hold:
T(0) = T(1) = 0
Comparison of Iterative and recursive version
Iterative method for loop executes n – 1 times
For each of n – 1 calls, the index Of Smallest is invoked, last is n-1, first ranges from 0 to n-2.
For each index Of Smallest, compares last – first times
Total operations: (n – 1) + (n – 2) + …+ 1 = n(n – 1)/2 = O(n2)
It does not depends on the nature of the data in the array.
Recursive selection sort performs same operations
Also O(n2)
Discussion on critical operation involved
Iterative Version:
Algorithm selectionSort(a, n)
// Sorts the first n elements of an array a.
for (index = 0; index < n - 1; index++)
{ indexOfNextSmallest = the index of the smallest value among
a[index], a[index+1], . . . , a[n-1]
Interchange the values of a[index] and a[indexOfNextSmallest]
// Assertion: a[0] £ a[1] £ . . . £ a[index], and these are the smallest
// of the original array elements.
// The remaining array elements begin at a[index+1].
}
Recursive Version:
Algorithm selectionSort(a, first, last)
// Sorts the array elements a[first] through a[last] recursively.
if (first < last)
{ indexOfNextSmallest = the index of the smallest value among
a[first], a[first+1], . . . , a[last]
Interchange the values of a[first] and a[indexOfNextSmallest]
// Assertion: a[0] £ a[1] £ . . . £ a[first] and these are the smallest
// of the original array elements.
// The remaining array elements begin at a[first+1].
selectionSort(a, first+1, last)
}
BigONotation Analysis
Same for both iterative and recursive version
BenchMark used:
public class BenchmarkSorts {
int a[]=new int[1000];
public BenchmarkSorts() {
for(int j=0;j<1000;j++)
{;
Random rn = new Random();
a[j] = rn.nextInt(10) + 1;
}
}
public void runSorts(){
SelectionSort s=new SelectionSort();
s.rescursiveSort(a);
s.iterativeSort(a);
}}
Graph Obtained
ned
Conclusion:
Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all n elements (this takes n 1 comparisons) and then swapping it into the first position.
Finding the next lowest element requires scanning the remaining n 1 elements and so on, for (n 1) + (n 2) + ... + 2 + 1 = n(n 1) / 2 (n2) comparisons. Each of these scans requires one swap for n 1 elements.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.