The purpose of this program is to compare the computing times of the two classic
ID: 3751504 • Letter: T
Question
The purpose of this program is to compare the computing times of the two classical sorting algorithms Mergesort and Quicksort where insertion sort Is used as a threshold sort. Although for large lists, Insertionsort is, on average, much slower than Mergesort and Quicksort, it is faster than both for sufficiently small lists. A useful technique to improve the efficiency of a divide-and conquer sorting algorithm is to employ a sorting algorithm such as Insertionsort when the input size is smaller than or equal to some threshold t (e.g., a number between 8 and 16 usually works well) Instead of the bootstrap condition being a list of size and simply doing nothing other than return when this condition is satisfied, the bootstrap condition is now a list of sizeExplanation / Answer
import java.util.Random;
import java.util.Scanner;
public class MergeOrQuick {
public static int comparisons = 0;
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
Random rand = new Random();
String documentation = "This program compares Mergesort and Quicksort using Insertionsort as the threshold sort. ";
documentation += "You will be asked for a threshold value. If the size of the array is less than the threshold, ";
documentation += "Insertion sort will be used for sorting. Else, first Merge sort will be used and then quick sort. ";
documentation += "Program will output the time taken for completing the algorithms. ";
documentation += "The program will guide you through the rest of the process ";
System.out.println(documentation);
System.out.println("Enter the threshold value: ");
int thresh = scn.nextInt();
boolean repeat = true;
while (repeat) {
System.out.println("Enter the size of list: ");
int size = scn.nextInt();
int[] arr = new int[size];
boolean manual = false;
if (size <= 10) {
System.out.println("Do you want to manually enter or randomly generate the list? (m or r)");
char choice = scn.next().charAt(0);
if (choice == 'm' || choice == 'M') {
manual = true;
}
}
if (manual) {
System.out.println("Enter the array: ");
for (int i = 0; i < size; i++) {
arr[i] = scn.nextInt();
}
} else {
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(1000);
}
}
boolean display = false;
System.out.println("Do you want to display the array? (y or n)");
char choice = scn.next().charAt(0);
if (choice == 'y' || choice == 'Y') {
display = true;
}
if (display) {
System.out.println("Unsorted array: ");
for (int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
boolean showComparison = false;
System.out.println("Do you want to show the number of comparisons in each algorithm? (y or n)");
choice = scn.next().charAt(0);
if (choice == 'y' || choice == 'Y') {
showComparison = true;
}
if (size < thresh) {
long start = System.currentTimeMillis();
comparisons= 0;
insertion(arr);
long end = System.currentTimeMillis();
System.out.println("Insertion sort took: " + (end - start) + "ms");
if (display) {
System.out.println("Sorted array(insertion sort): ");
for (int i = 0; i < size; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
if (showComparison) {
System.out.println("No of comparisons: " + comparisons);
}
} else {
long start = System.currentTimeMillis();
comparisons = 0;
int[] sorted = mergeSort(arr, 0, arr.length - 1);
long end = System.currentTimeMillis();
System.out.println("Merge sort took: " + (end - start) + "ms");
if (display) {
System.out.println("Sorted array (merge sort): ");
for (int i = 0; i < size; i++) {
System.out.print(sorted[i] + " ");
}
System.out.println();
}
if (showComparison) {
System.out.println("No of comparisons: " + comparisons);
}
start = System.currentTimeMillis();
comparisons = 0;
quickSort(arr, 0, arr.length - 1);
end = System.currentTimeMillis();
System.out.println("Quick sort took: " + (end - start) + "ms");
if (display) {
System.out.println("Sorted array (quick sort): ");
for (int i = 0; i < size; i++) {
System.out.print(sorted[i] + " ");
}
System.out.println();
}
if (showComparison) {
System.out.println("No of comparisons: " + comparisons);
}
}
System.out.println("Do you want to repeat? (y or n)");
choice = scn.next().charAt(0);
if (choice == 'n' || choice == 'N') {
repeat = false;
}
}
}
public static void insertion(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int val = arr[i], j;
for (j = i - 1; j >= 0 && arr[j] > val; j--) {
arr[j + 1] = arr[j];
comparisons++;
}
arr[j + 1] = val;
}
}
public static int[] mergeSort(int[] arr, int lo, int hi) {
if (lo == hi) {
int[] br = new int[1];
br[0] = arr[lo];
return br;
}
int mid = (lo + hi) / 2;
int[] fh = mergeSort(arr, lo, mid);
int[] sh = mergeSort(arr, mid + 1, hi);
int[] merge = mergeTwoSortedArrays(fh, sh);
return merge;
}
public static int[] mergeTwoSortedArrays(int[] arr1, int[] arr2) {
int merged[] = new int[arr1.length + arr2.length];
int i = 0, j = 0, k = 0;
while (i < arr1.length && j < arr2.length) {
comparisons++;
if (arr1[i] <= arr2[j]) {
merged[k] = arr1[i];
i++;
k++;
} else {
merged[k] = arr2[j];
j++;
k++;
}
}
if (i == arr1.length) {
while (j < arr2.length) {
merged[k] = arr2[j];
j++;
k++;
}
} else {
while (i < arr1.length) {
merged[k] = arr1[i];
i++;
k++;
}
}
return merged;
}
public static void quickSort(int[] arr, int lo, int hi) {
if (lo >= hi) {
return;
}
int mid = (lo + hi) / 2;
int pivot = arr[mid];
int left = lo;
int right = hi;
while (left <= right) {
while (arr[left] < pivot) {
left++;
comparisons++;
}
while (arr[right] > pivot) {
right--;
comparisons++;
}
if (left <= right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
quickSort(arr, lo, right);
quickSort(arr, left, hi);
}
}
OUTPUT:
This program compares Mergesort and Quicksort using Insertionsort as the threshold sort.
You will be asked for a threshold value. If the size of the array is less than the threshold,
Insertion sort will be used for sorting. Else, first Merge sort will be used and then quick sort.
Program will output the time taken for completing the algorithms.
The program will guide you through the rest of the process
Enter the threshold value:
9
Enter the size of list:
10
Do you want to manually enter or randomly generate the list? (m or r)
r
Do you want to display the array? (y or n)
y
Unsorted array:
244 265 653 220 316 460 211 756 809 865
Do you want to show the number of comparisons in each algorithm? (y or n)
y
Merge sort took: 0ms
Sorted array (merge sort):
211 220 244 265 316 460 653 756 809 865
No of comparisons: 22
Quick sort took: 0ms
Sorted array (quick sort):
211 220 244 265 316 460 653 756 809 865
No of comparisons: 15
Do you want to repeat? (y or n)
y
Enter the size of list:
100
Do you want to display the array? (y or n)
n
Do you want to show the number of comparisons in each algorithm? (y or n)
y
Merge sort took: 0ms
No of comparisons: 543
Quick sort took: 0ms
No of comparisons: 503
Do you want to repeat? (y or n)
y
Enter the size of list:
1000
Do you want to display the array? (y or n)
n
Do you want to show the number of comparisons in each algorithm? (y or n)
y
Merge sort took: 2ms
No of comparisons: 8714
Quick sort took: 2ms
No of comparisons: 6716
Do you want to repeat? (y or n)
y
Enter the size of list:
5000
Do you want to display the array? (y or n)
n
Do you want to show the number of comparisons in each algorithm? (y or n)
y
Merge sort took: 15ms
No of comparisons: 55242
Quick sort took: 1ms
No of comparisons: 40957
Do you want to repeat? (y or n)
y
Enter the size of list:
10000
Do you want to display the array? (y or n)
n
Do you want to show the number of comparisons in each algorithm? (y or n)
y
Merge sort took: 3ms
No of comparisons: 120441
Quick sort took: 2ms
No of comparisons: 90223
Do you want to repeat? (y or n)
y
Enter the size of list:
10000
Do you want to display the array? (y or n)
n
Do you want to show the number of comparisons in each algorithm? (y or n)
y
Merge sort took: 3ms
No of comparisons: 120493
Quick sort took: 2ms
No of comparisons: 81577
Do you want to repeat? (y or n)
y
Enter the size of list:
50000
Do you want to display the array? (y or n)
n
Do you want to show the number of comparisons in each algorithm? (y or n)
y
Merge sort took: 16ms
No of comparisons: 718189
Quick sort took: 7ms
No of comparisons: 400094
Do you want to repeat? (y or n)
y
Enter the size of list:
100000
Do you want to display the array? (y or n)
n
Do you want to show the number of comparisons in each algorithm? (y or n)
y
Merge sort took: 34ms
No of comparisons: 1536292
Quick sort took: 15ms
No of comparisons: 900975
Do you want to repeat? (y or n)
n
DISCUSSION:
After repeating the code for a lot of other threshold values, we conclude that, insertion sort quickly starts taking more time to sort the array.
We can conclude that insertion sort is not a very efficient problem. It works fine till n = 1000. But after that, it starts taking a lot of time and comparisons. For n = 105 insertion sort makes so many comparisons that the counter overflows and we get a negative number.
Merge sort and quick sort are efficient algorithms. They take less than 1 sec for very large array size. And their number o comparisons are also significantly less than insertion sort. But if we compare merge sort with quick sort, we observe that quick sort is slightly better than merge sort, based on time taken and number of comparisons.
No. of comparisons: 32 Time taken: 0ms
No of comparisons: 21 Time taken: 0ms
No of comparisons: 16 100 Time taken: 0ms
No of comparisons: 2535 Time taken: 0ms
No of comparisons: 544 Time taken: 0ms
No of comparisons: 374 1000 Time taken: 10ms
No of comparisons: 253783 Time taken: 2ms
No of comparisons: 8705 Time taken: 1ms
No of comparisons: 6493 5000 Time taken: 50ms
No of comparisons: 6286453 Time taken: 2ms
No of comparisons: 55180 Time taken: 1ms
No of comparisons: 46028 100000 Time taken: 7511ms
No of comparisons: -1801797414 Time taken: 42ms
No of comparisons: 1536190 Time taken: 17ms
No of comparisons: 932162
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.