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=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= 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
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]));
}
}
Runtime Testing :
The method public static void compare(int n) creates arrays of integers of size n
that contain random integers between -10000 and 10000. It runs each of the sorting
to determine how the different sorting algorithms compare in practice. The
ComparisonSorter calls the compare method from its main method passing in the first
command line argument for the value n in the compare function. To run classes with
command line arguments in Eclipse, you will need to configure the run configuration for the
class.
Can you please do the Runtime Testing for above code?
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
