Evaluating and comparing efficiency of sorting algorithms Requirements: Compare
ID: 665586 • Letter: E
Question
Evaluating and comparing efficiency of sorting algorithms
Requirements: Compare the efficiency of Selection Sort, Insertion Sort and Quicksort.
Approach: Starting from your second third homework assignment, evaluate the efficiency of Selection Sort, Insertion Sort and Quicksort. For doing this, you should evaluate their corresponding implementations in each of the 3 cases (best, worst, and average) and count the number of operations performed (assignments, comparisons, and overall, separately). For counting them, you need to add in the right place specific statements to increment the counters for assignments and/or comparisons, wherever needed (actually you have to add for Quicksort only, in case you received no feedback for review/update/change the counters from the second homework assignment).
Draw charts to show how the running time (estimated in numbers of assignments A(n), comparisons C(n), and overall time T(n)=A(n) + C(n)) growths as the size of the input data n is growing. To draw the charts, vary the input size (n) between 100 and 1000, with an increment of maximum 100. For each size, generate the appropriate input sequence (best, worst, or average) for the specific sorting method (be aware: best/worst cases are not necessary the same for the three algorithms), run it, and store the values (A(n), C(n), T(n)).
For the average case, you have to repeat the measurements m times (m=5 should suffice) and report their average. Moreover, for the average case, make sure you always use the same input sequence for all three sorting methods for a fair comparison.
For each of the analyzed cases, generate charts which compare the three methods; use different charts for the number of comparisons, number of assignments and total number of operations. Name your charts and curves on each chart appropriately (that is, specify what the chart/curve represents).
Deliverables: You should submit (1) all the source (.java) files, (2) the diagrams (the easiest way to draw them is by using Microsoft Excel Worksheet) and (3) a document file describing your solution. The solution description document should include the following elements: justification for the added statements (the ones that increment the counters), the choice for the input data for best and worst cases for each algorithm, with justification, the interpretation of the diagrams and lessons learned. The size of the document should be of 2-4 pages, single spaced, font size 12. All solution description elements should be properly formatted using APA style.
Explanation / Answer
Selection Sort
import java.util.*;
public class MySelectionSort {
public static ArrayList<Integer> doSelectionSort(ArrayList<Integer> arr){
int count = 0;
for (int i = 0; i < arr.size() - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.size(); j++){
if (arr.get(j) < arr.get(index))
index = j;
count += 1;
}
int smallerNumber = arr.get(index);
arr.set(index, arr.get(i));
arr.set(i, smallerNumber);
}
System.out.println("the number of operations are :-");
System.out.print(count);
System.out.println("");
return arr;
}
public static void main(String a[]){
System.out.println("enter the count of numbers you want to sort");
int n;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
ArrayList<Integer> arr= new ArrayList<>();
System.out.println("enter the numbers");
int k;
for(int i = 0;i < n;i++){
k = sc.nextInt();
arr.add(k);
}
ArrayList<Integer> arr2 = doSelectionSort(arr);
for(int i = 0;i < n; i++){
System.out.print(arr2.get(i) + " ");
}
}
}
Insertion Sort
import java.util.ArrayList;
import java.util.Scanner;
public class MyInsertionSort {
public static ArrayList<Integer> doInsertionSort(ArrayList<Integer> input){
int temp, count = 0;
for (int i = 1; i < input.size(); i++) {
for(int j = i ; j > 0 ; j--){
if(input.get(j) < input.get(j-1)){
temp = input.get(j);
input.set(j, input.get(j-1));
input.set(j-1, temp) ;
count++;
}
}
}
System.out.println("the number of operations are :-");
System.out.print(count);
System.out.println("");
return input;
}
public static void main(String a[]){
System.out.println("enter the count of numbers you want to sort");
int n;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
ArrayList<Integer> arr= new ArrayList<>();
System.out.println("enter the numbers");
int k;
for(int i = 0;i < n;i++){
k = sc.nextInt();
arr.add(k);
}
ArrayList<Integer> arr2 = doInsertionSort(arr);
for(int i = 0;i < n; i++){
System.out.print(arr2.get(i) + " ");
}
}
}
Quick Sort
public class MyQuickSort {
private int array[];
private int length;
public int sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return 0;
}
this.array = inputArr;
length = inputArr.length;
return quickSort(0, length - 1);
}
private int quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
int count = 0;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
count++;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
count += quickSort(lowerIndex, j);
if (i < higherIndex)
count += quickSort(i, higherIndex);
return count;
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
MyQuickSort sorter = new MyQuickSort();
int[] input = {24,2,45,20,56,75,2,56,99,53,12}; // change the numbers here
int count = sorter.sort(input);
System.out.println("number of operations are " + count);
System.out.println("the sorted output is ");
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.