You are going to demonstrate your understanding with the three sorting algorithm
ID: 3828552 • 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.
You have the following list of numbers to sort: [54, 26, 93, 17, 77, 31, 44, 55, 15]
1. 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.
[Thorough Explanation would be much Appreciated]
CODE:
Explanation / Answer
Hi, Please fin dmy implementation.
I have added a fied to keep count of comparision.
######
public class SelectionSort
{
public static int comparisonCount = 0;
public static void main(String[] args)
{
int[] A = new int[] { 54, 26, 93, 17, 77, 31, 44, 55, 12 };
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("Number of comparisions in Quick Sort: "+SelectionSort.comparisonCount);
}
public 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++)
{
comparisonCount++;
if (A[index] > A[maxIndex])
maxIndex = index;
}
int temp = A[maxIndex];
A[maxIndex] = A[last];
A[last] = temp;
}
}
} //END
/*
Sample run:
Original order:
54 26 93 17 77 31 44 55 12
After sorting:
12 17 26 31 44 54 55 77 93
Number of comparisions in Quick Sort: 36
*/
##########
public class InsertionSort
{
public static int comparisonCount = 0;
public static void main(String[] args)
{
int[] A = new int[] { 54, 26, 93, 17, 77, 31, 44, 55, 12 };
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("Number of comparisions in Quick Sort: "+InsertionSort.comparisonCount);
}
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;
comparisonCount++;
while (scan > 0 && A[scan -1] > unSortedValue)
{
comparisonCount++;
A[scan] = A[scan - 1];
scan--;
}
A[scan] = unSortedValue;
}
}
} //END
/*
Sample run:
Original order:
54 26 93 17 77 31 44 55 12
After sorting:
12 17 26 31 44 54 55 77 93
Number of comparisions in Quick Sort: 29
*/
##########
import java.util.*;
public class QuickSorter
{
public static int comparisonCount = 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 ++)
{
comparisonCount++;
if (A[scan] < pivotValue)
{
endOfLeftList ++;
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;
}
}//END
######
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, 12 };
// Display the array's contents.
System.out.println("Original order: " + Arrays.toString(A));
// Sort the array.
QuickSorter.quickSort(A);
System.out.println();
System.out.println("After sorting: " + Arrays.toString(A));
System.out.println("Number of comparisions in Quick Sort: "+QuickSorter.comparisonCount);
}
}//END
/*
Sample run:
Original order:
[54, 26, 93, 17, 77, 31, 44, 55, 12]
After sorting:
[12, 17, 26, 31, 44, 54, 55, 77, 93]
Number of comparisions in Quick Sort: 18
*/
Clearly. Quick Sort is taking less comparisons.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.