1. Implement the merge-sort algorithm
a. Determine the correct basic operation
2. Test your algorithm on inputs of size 2^10, 2^11 ... 2^20.
If this is too slow then just run it on any set of powers of two.
3. Show the running time of each of these inputs
Choose a basic operation
Count the total number times that this basic operation is done for each
power of 2.
Display this count in a table
Since you have not mentioned the language of your preference, I am providing the code in JAVA,
CODE
import java.util.Random;
import java.util.Scanner;
public class Main
{
public static void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int L[] = new int [n1];
int R[] = new int [n2];
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
public static void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = (l+r)/2;
mergeSort(arr, l, m);
mergeSort(arr , m+1, r);
merge(arr, l, m, r);
}
}
public static void printArray(int arr[]) {
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
for (int k=10; k<=20; k++) {
int n = (int) Math.pow(2, k);
int a[] = new int[n];
int temp[] = new int[n];
Random rand = new Random();
for(int i=0; i<n; i++) {
a[i] = rand.nextInt(100);
}
for(int i=0; i<n; i++) {
temp[i] = a[i];
}
long startTime, endTime, duration;
a = temp;
startTime = System.nanoTime();
mergeSort(a, 0, a.length-1);
endTime = System.nanoTime();
duration = (endTime - startTime) / 1000000;
System.out.println("For n = " + n + ", Merge Sort took " + duration + " milliseconds\n");
}
sc.close();
}
}
1. Implement the merge-sort algorithm a. Determine the correct basic operation 2. Test your algorithm on...
Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into two parts like Merge sort, 4-way Merge sort splits the array into four parts. 4-way Merge divides the input array into fourths, calls itself for each fourth and then merges the four sorted fourths. a)Implement 4-way Merge sort from Problem 4 to sort an array/vector of integers and name it merge4. Implement the algorithm in the same language you used for the sorting algorithms...
1. Write a Java program to implement Counting Sort and write a driver to test it. Note: use random number generator to generate your input with n = 10, 50, and 100. Verify that the running time is O(n). 2. Write a Java program to implement Bucket Sort and write a driver to test it. Note: use random number generator to generate your input with n = 10, 50, and 100. Verify that the running time is O(n). 3. In...
Implement MERGE-SORT() algorithm that reads from a file named “inputHW02.txt” a list of double numbers (max = 3,000,000 numbers), sorts those numbers and indicates time consumption. This programming question will address the advantage of using iteration loops over recursive calls as well as using INSERTION-SORT() as a procedure in MERGESORT(). Your program must perform the following actions: 1. Opens the given file name and reads all double numbers. For simplicity, we assume this file only contains numbers and nothing else....
DESCRIPTION Implement a program in C++ that generates a specified number of random integers, records them in three arrays, then sorts the arrays with Insertion Sort, Merge Sort, and Quick Sort, respectively. Augment the three sorting algorithms with counters and report the number of characteristic operations each performs in sorting the (same) random values. INPUT The program reads from the terminal the number of random integers to generate, a seed value for the pseudo-random number generator, and a character that...
Part B (BI). Implement a Red-Black tree with only operation Insert(). Your program should read from a file that contain positive integers and should insert those numbers into the RB tree in that order. Note that the input file will only contain distinct integers. Print your tree by level using positive values for Black color and negative values for Red color Do not print out null nodes. Format for a node: <Node_value>, <Parent_value>). For example, the following tree is represented...
2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A (7,3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array. 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 4. Gi pseudocode for an algorithm that will solve the following...
Practical 5: Write a program that implements several sorting algorithms, and use it to demonstrate the comparative performance of the algorithms for a variety of data sets. Need Help With this Sorting Algorithm task for C++ Base Code for sorting.cpp is given. The header file is not included in this. Help would be much appreciated as I have not started on this due to personal reasons #include <cstdlib> #include <iostream> #include <getopt.h> using namespace std; long compares; // for counting...
Subject: Algorithm need this urgent please. 2.1 Searching and Sorting- 5 points each 1. Run Heapsort on the following array: A 17, 3, 9, 4, 2,5, 6, 1,8) 2. Run merge sort on the same array 3. What is the worst case for quick sort? What is the worst case time com- plexity for quick sort and why? Explain what modifications we can make to quick sort to make it run faster, and why this helps. 2.1 Searching and Sorting-...
For each of the following, give the correct answer by circling one of the two choices. TRUE or FALSE. The average-ease running time of an algorithm, over all inputs of size n, is always more than its worst-ease running time. TRUE FALSE log_b(a * c) = log_b a* log_b c. TRUE FALSE Stacks support insertions and deletions in the first-in first-out (FIFO) principle.TRUE FALSE An array of size n can support insertAtRank operation in worst-ease O(1) time.TRUE FALSE A heap...