Now implement similar methods to test special cases for sorting. You can use my compare method as a guide. Feel free to comment out the original compare method when you are running these methods. Add these results to your table. public static void compareSorted (int n) This method creates arrays of integers 1 to n in sorted order and runs the different sorting algorithms on the arrays. public static void compareReverse Sorted (int n) This method creates an array of integers 1 to n in reverse sorted order and runs the different sorting algorithms on the arrays. public static void compare Duplicates (int n) This method creates an array of n 1s and runs the different sorting algorithms on the arrays.
package sorting;
import java.util.Arrays;
import java.util.Random;
import sorting.Heap;
public class ComparisonSorter {
public static void insertionSort(int[] arr) {
for(int i=1;i<arr.length;i++) {
int j = i-1;
int toPlace = arr[i];
while(j>=0&&arr[j]>toPlace) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = toPlace;
}
}
public static void mergeSort(int [] arr) {
mergeSortRecurse(arr,0,arr.length-1);
}
private static void mergeSortRecurse(int[] arr, int start, int end) {
if(start>=end)
return;
int mid = start + ((end-start)/2);
mergeSortRecurse(arr,start,mid);
mergeSortRecurse(arr,mid+1,end);
merge(arr,start,mid,end);
}
private static void merge(int[] arr, int start, int mid, int end) {
int leftSize = mid - start +1;
int rightSize = end - mid;
int[] left = new int[leftSize+1];
int[] right = new int[rightSize+1];
int leftIndex;
int rightIndex;
for(leftIndex = 0; leftIndex<leftSize;leftIndex++)
left[leftIndex] = arr[start+leftIndex];
for(rightIndex = 0; rightIndex<rightSize;rightIndex++)
right[rightIndex] = arr[mid+rightIndex+1];
left[leftIndex] = Integer.MAX_VALUE;
right[rightIndex] = Integer.MAX_VALUE;
leftIndex = 0;
rightIndex = 0;
for(int mergeIndex = start; mergeIndex<=end;mergeIndex++) {
if(left[leftIndex] <= right[rightIndex]) {
arr[mergeIndex] = left[leftIndex];
leftIndex++;
}
else {
arr[mergeIndex] = right[rightIndex];
rightIndex++;
}
}
}
public static void heapSort(int[] arr)
{
// create a new instance of Heap using the given array
Heap heap = new Heap(arr, arr.length);
// build a max heap from the array
heap.buildMaxHeap();
// repeatedly extract the maximum element from the heap and place it at the end of the array
for (int i = arr.length - 1; i >= 1; i--) {
// swap the maximum element with the last element of the heap
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// reduce the heap size to exclude the last element
heap.setHeapSize(heap.getHeapSize() - 1);
// restore the max heap property
heap.maxHeapify(0);
}
}
public static int partitionLomuto(int[] arr, int low, int high) {
int pivot = arr[high]; // Choose the last element as the pivot
int i = low - 1; // Initialize the index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp; // Swap arr[i] and arr[j]
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp; // Swap arr[i + 1] and arr[high], which is the pivot
return i + 1; // Return the partition index
}
public static void quickSortLomuto(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partitionLomuto(arr, low, high);
quickSortLomuto(arr, low, pivotIndex - 1); // Sort the left subarray
quickSortLomuto(arr, pivotIndex + 1, high); // Sort the right subarray
}
}
public static void quickSort(int[] arr)
{
quickSortLomuto(arr, 0, arr.length - 1);
}
public static void compare(int n) {
int[] insertionData = new int[n];
int[] mergeData = new int[n];
int[] heapData = new int[n];
int[] quickData = new int[n];
long start;
long end;
long runtime;
Random randomGenerator = new Random();
for(int i=0;i<n;i++) {
int j = randomGenerator.nextInt()%10001;
insertionData[i] = mergeData[i] = heapData[i] = quickData[i] = j;
}
start = System.nanoTime();
insertionSort(insertionData);
end = System.nanoTime();
runtime = end - start;
System.out.println("Insertion Sort took: " + runtime);
start = System.nanoTime();
mergeSort(mergeData);
end = System.nanoTime();
runtime = end - start;
System.out.println("Merge Sort took: " + runtime);
start = System.nanoTime();
heapSort(heapData);
end = System.nanoTime();
runtime = end - start;
System.out.println("Heap Sort took: " + runtime);
start = System.nanoTime();
quickSort(quickData);
end = System.nanoTime();
runtime = end - start;
System.out.println("QuickSort took: " + runtime);
}
public static void main(String[] args) {
compare(Integer.parseInt(args[0]));
}
}
Can you please help Written Prediction and Testing above the code?
![Predict the order in which the algorithms will perform in practice and explain your
reasoning. You can predict that some algorithms will tie. Your reasoning should include the
runtime of each algorithm.
Create a table that compares the runtimes of the different sorting algorithms on
randomized inputs of sizes starting at 10 and increasing by a power of 10 as high as your
computer can go. You don't need to run your code forever, but expect some of the larger
sized inputs to take several minutes. For example it took my machines about 4 minutes to
run the timing method on all four sorting algorithms with input size of 1,000,000.
Now implement similar methods to test special cases for sorting. You can use my compare
method as a guide. Feel free to comment out the original compare method when you are
running these methods. Add these results to your table.
public static void compare Sorted (int n)
This method creates arrays of integers 1 to n in sorted order and runs the different sorting
algorithms on the arrays.
public static void compare Reverse Sorted (int n)
This method creates an array of integers 1 to n in reverse sorted order and runs the
different sorting algorithms on the arrays.
public static void compare Duplicates (int n)
This method creates an array of n 1s and runs the different sorting algorithms on the
arrays.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F165f5551-99fc-4800-9810-1597ce53807c%2Fbd48dc04-758f-408e-b497-477d9c0f86eb%2Fnq7jty8_processed.png&w=3840&q=75)
![](/static/compass_v2/shared-icons/check-mark.png)
Trending now
This is a popular solution!
Step by step
Solved in 8 steps with 1 images
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![Database System Concepts](https://www.bartleby.com/isbn_cover_images/9780078022159/9780078022159_smallCoverImage.jpg)
![Starting Out with Python (4th Edition)](https://www.bartleby.com/isbn_cover_images/9780134444321/9780134444321_smallCoverImage.gif)
![Digital Fundamentals (11th Edition)](https://www.bartleby.com/isbn_cover_images/9780132737968/9780132737968_smallCoverImage.gif)
![C How to Program (8th Edition)](https://www.bartleby.com/isbn_cover_images/9780133976892/9780133976892_smallCoverImage.gif)
![Database Systems: Design, Implementation, & Manag…](https://www.bartleby.com/isbn_cover_images/9781337627900/9781337627900_smallCoverImage.gif)
![Programmable Logic Controllers](https://www.bartleby.com/isbn_cover_images/9780073373843/9780073373843_smallCoverImage.gif)