You are going to demonstrate your understanding with the three sorting algorithm
ID: 3831082 • Letter: Y
Question
You are going to demonstrate your understanding with the three sorting algorithms by showing their executions. The algorithms are: Selection, Insertion, and Quicksort sorts. For the consistency of the evaluation, please use the only the algorithms we discussed in our lecture.
1. You have the following list of numbers to sort (10 points): [54, 26, 93, 17, 77, 31, 44, 55, 36] You need to show all execution passes of the algorithms, in a table row format, with the exception of Quick Sort. *******************************************************************************************
import java.util.Arrays;
public class QuickSort
{
public static void main(String[] args)
{
// Create an int array with test values.
int[] A = { 54, 26, 93, 17, 77, 31, 44, 55, 36 };
// Display the array's contents.
System.out.println("Original order: " + Arrays.toString(A));
// Sort the array.
QuickSorter.quickSort(A);
System.out.println("After sorting: " + Arrays.toString(A));
System.out.println("QuickSort Comparisons:"+QuickSorter.getComp());
}
}
*******************************************************************************************
public class SelectionSort {
private static int comp=0;
public static void main(String[] args) {
int[] A = { 54, 26, 93, 17, 77, 31, 44, 55, 36};
System.out.println("Original order: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
selectionSort(A);
System.out.println("After sorting: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
System.out.println("SelectionSort Comparisons:"+comp);
}
private static void selectionSort(int[] A) {
int N = A.length;
for (int last = N - 1; last >= 1; last--) {
int maxIndex = 0;
for (int index = 1; index <= last; index++) {
if (A[index] > A[maxIndex]){
maxIndex = index;
comp++;
}
}
int temp = A[maxIndex];
A[maxIndex] = A[last];
A[last] = temp;
}
}
}
*******************************************************************************************
import java.util.*;
public class QuickSorter {
private static int comp=0;
public static void quickSort(int array[]) {
doQuickSort(array, 0, array.length - 1);
}
private static void doQuickSort(int array[], int start, int end) {
int pivotPoint;
if (start < end) {
int beforePivotPoint[] = Arrays.copyOfRange(array, start, end + 1);
pivotPoint = partition(array, start, end);
doQuickSort(array, start, pivotPoint - 1);
doQuickSort(array, pivotPoint + 1, end);
}
}
private static int partition(int A[], int start, int end) {
int pivotValue = A[start];
int endOfLeftList = start;
for (int scan = start + 1; scan <= end; scan++) {
if (A[scan] < pivotValue) {
endOfLeftList++;
comp++;
swap(A, endOfLeftList, scan);
}
}
swap(A, start, endOfLeftList);
return endOfLeftList;
}
private static void swap(int[] A, int a, int b) {
int temp;
temp = A[a];
A[a] = A[b];
A[b] = temp;
}
public static int getComp(){
return comp;
}
}
*******************************************************************************************
public class InsertionSort {
private static int comp=0;
public static void main(String[] args) {
int[] A = { 54, 26, 93, 17, 77, 31, 44, 55, 36 };
System.out.println("Original order: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
insertionSort(A);
System.out.println("After sorting: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
System.out.println("InsertionSort Comparisons:"+comp);
}
private static void insertionSort(int[] A) {
int N = A.length;
for (int index = 1; index <= N - 1; index++) {
int unSortedValue = A[index];
int scan = index;
while (scan > 0 && A[scan - 1] > unSortedValue) {
A[scan] = A[scan - 1];
scan--;
comp++;
}
A[scan] = unSortedValue;
}
}
}
2. Using the data provided, which of the above algorithm is more efficient and why? Hints: Please consider counting the number of comparisons made by each algorithm. Do not count the number of passes. Please show your work and motivate your answer.
Explanation / Answer
Ans-1:
ouputs:
Insertion sort:
Original order:
54 26 93 17 77 31 44 55 36
pass: 1
26 54 93 17 77 31 44 55 36
pass: 2
26 54 93 17 77 31 44 55 36
pass: 3
17 26 54 93 77 31 44 55 36
pass: 4
17 26 54 77 93 31 44 55 36
pass: 5
17 26 31 54 77 93 44 55 36
pass: 6
17 26 31 44 54 77 93 55 36
pass: 7
17 26 31 44 54 55 77 93 36
pass: 8
17 26 31 36 44 54 55 77 93
After sorting:
17 26 31 36 44 54 55 77 93
InsertionSort Comparisons:26
Selection sort outputs:
Original order:
54 26 93 17 77 31 44 55 36
pass: 1
54 26 36 17 77 31 44 55 93
pass: 2
54 26 36 17 55 31 44 77 93
pass: 3
54 26 36 17 44 31 55 77 93
pass: 4
31 26 36 17 44 54 55 77 93
pass: 5
31 26 36 17 44 54 55 77 93
pass: 6
31 26 17 36 44 54 55 77 93
pass: 7
17 26 31 36 44 54 55 77 93
pass: 8
17 26 31 36 44 54 55 77 93
After sorting:
17 26 31 36 44 54 55 77 93
SelectionSort Comparisons:36
quicksort ouputs:
Original order:
[54, 26, 93, 17, 77, 31, 44, 55, 36]
After sorting:
[17, 26, 31, 36, 44, 54, 55, 77, 93]
QuickSort Comparisons:17
QuickSort.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package sorting;
/**
*
* @author abc
*/
import java.util.Arrays;
public class QuickSort {
/**
* @param args the command line arguments
*/
public static void main(String[] args)
{
// Create an int array with test values.
int[] A = { 54, 26, 93, 17, 77, 31, 44, 55, 36 };
// Display the array's contents.
System.out.println("Original order: " + Arrays.toString(A));
// Sort the array.
QuickSorter.quickSort(A);
System.out.println("After sorting: " + Arrays.toString(A));
System.out.println("QuickSort Comparisons:"+QuickSorter.getComp());
}
}
QuickSorter.java
package sorting;
import java.util.*;
public class QuickSorter {
private static int comp=0;
public static void quickSort(int array[]) {
doQuickSort(array, 0, array.length - 1);
}
private static void doQuickSort(int array[], int start, int end) {
int pivotPoint;
if (start < end) {
int beforePivotPoint[] = Arrays.copyOfRange(array, start, end + 1);
pivotPoint = partition(array, start, end);
doQuickSort(array, start, pivotPoint - 1);
doQuickSort(array, pivotPoint + 1, end);
}
}
private static int partition(int A[], int start, int end) {
int pivotValue = A[start];
int endOfLeftList = start;
for (int scan = start + 1; scan <= end; scan++) {
if (A[scan] < pivotValue) {
endOfLeftList++;
swap(A, endOfLeftList, scan);
}
comp++;
}
swap(A, start, endOfLeftList);
return endOfLeftList;
}
private static void swap(int[] A, int a, int b) {
int temp;
temp = A[a];
A[a] = A[b];
A[b] = temp;
}
public static int getComp(){
return comp;
}
}
-----------------------------
InsertionSort.java
public class InsertionSort {
private static int comp=0;
public static void main(String[] args) {
int[] A = { 54, 26, 93, 17, 77, 31, 44, 55, 36 };
System.out.println("Original order: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
insertionSort(A);
System.out.println("After sorting: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
System.out.println("InsertionSort Comparisons:"+comp);
}
private static void display(int[] A)
{
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
}
private static void insertionSort(int[] A) {
int N = A.length;
int pass=1;
for (int index = 1; index <= N - 1; index++) {
int unSortedValue = A[index];
int scan = index;
while (scan > 0 && A[scan - 1] > unSortedValue) {
A[scan] = A[scan - 1];
scan--;
comp++;
}
comp++;
A[scan] = unSortedValue;
System.out.println("pass: "+pass);
display(A);
pass++;
}
}
}
--------
SelectionSort.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package sorting;
/**
*
* @author abc
*/
public class SelectionSort {
private static int comp=0;
public static void main(String[] args) {
int[] A = { 54, 26, 93, 17, 77, 31, 44, 55, 36};
System.out.println("Original order: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
selectionSort(A);
System.out.println("After sorting: ");
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
System.out.println("SelectionSort Comparisons:"+comp);
}
private static void display(int[] A)
{
for (int i = 0; i < A.length; i++)
System.out.print(A[i] + " ");
System.out.println(" ");
}
private static void selectionSort(int[] A) {
int N = A.length;
int pass=1;
for (int last = N - 1; last >= 1; last--) {
int maxIndex = 0;
for (int index = 1; index <= last; index++) {
if (A[index] > A[maxIndex]){
maxIndex = index;
}
comp++;
}
int temp = A[maxIndex];
A[maxIndex] = A[last];
A[last] = temp;
System.out.println("pass: "+pass);
display(A);
pass++;
}
}
}
--------------------------
Ans-2:
Consider selection sort ,selecting the lowest(largest) element requires scanning all n elements (this takes n 1 comparisons) and then swapping it into the first(last) 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 (n^2) comparisons, So in our case it took 9*8/2=36 comaprisions,so the worst case and average case time complexity is O(n^2)
consider the case insertion sort :
Worst Case Time Complexity : O(n^2)
Best Case Time Complexity : O(n)
Average Time Complexity : O(n^2)
Like selection sort, insertion sort loops over the indices of the array. It just calls insert on the elements at indices 1, 2, 3,....,n-1. Just as each call took an amount of time that depended on the size of the sorted subarray, so does each call to insert.Insertion Sort needs a minimum of (n-1) comparisons, and hence their best case running time is O(n),but we will consider only average case.
But in case of quick sort the average case is O(nlogn)
and the worst case takes O(n^2)
So quick sort is better than other two algorithms.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.