Question

Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into...

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 in HW 1. Your program should be able to read inputs from a file called “data.txt” where the first value of each line is the number of integers that need to be sorted, followed by the integers (like in HW 1). The output will be written to a file called “merge4.txt”.

b) Modify code- Now that you have verified that your code runs correctly using the data.txt input file, you can modify the code to collect running time data. Instead of reading arrays from the file data.txt and sorting, you will now generate arrays of size n containing random integer values from 0 to 10,000 to sort. Use the system clock to record the running times of each algorithm for ten different values of n for example: n = 5000, 10000, 15000, 20,000, …, 50,000. You may need CS 325 - Homework Assignment 2 to modify the values of n if an algorithm runs too fast or too slow to collect the running time data (do not collect times over a minute). Output the array size n and time to the terminal. Name the new program merge4Time.

c) Collect running times - Collect your timing data on the engineering server. You will need at least eight values of t (time) greater than 0. If there is variability in the times between runs of the same algorithm you may want to take the average time of several runs for each value of n. Create a table of running times.

d) Plot data and fit a curve - Plot the data you collected on an individual graph with n on the x-axis and time on the y-axis. You may use Excel, Matlab, R or any other software. What type of curve best fits each data set? Give the equation of the curves that best “fits” the data and draw that curves on the graphs.

e) Combine - Also plot the data from 4-way Merge sort together on a combined graph with your results for merge and insertion sort from HW1.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Pseudocode for 4-way Merge sort

B) there are total of 2*n-3 comparison where n is the size of your array

so for comparison complexity will be O(n).

mergeSort function devides this problem in 4 subproblems in size of (n/4) so recurrence relation will be

According to masters Theorem complexity of this algorithm is

c) Implementation in Python

def merge(A, l,m2,m1, m3, h):
    n1 = m2 - l + 1#calculating length of subarrays
    n2 = m1- m2
    n3 = m3-m1
    n4 = h-m3
    Ln = m1-l+1
    Rn = h-m1  
    # creating temporary arrays
    a = [0] * (n1)
    b = [0] * (n2)
    c = [0] * (n3)
    d = [0] * (n4)
    L = [0] * (Ln)
    R = [0] * (Rn)
    # Copy data to temp arrays L[] and R[]
    for i in range(0 , n1):
        a[i] = A[l + i]
    for i in range(0 , n2):
        b[i] = A[m2+1 + i]
    for i in range(0 , n3):
        c[i] = A[m1+1 + i]
    for i in range(0 , n4):
        d[i] = A[m3+1 + i]
    i1=0
    i2=0
    k=0
    while i1 < n1 and i2 < n2 :#merging first two part
        if a[i1] <= b[i2]:
            L[k] = a[i1]
            i1 += 1
        else:
            L[k] = b[i2]
            i2 += 1
        k += 1
    while i1 < n1:
        L[k] = a[i1]
        i1 += 1
        k += 1

    while i2 < n2:
        L[k] = b[i2]
        i2 += 1
        k += 1
    i1=0
    i2=0
    k=0
    while i1 < n3 and i2 < n4 :
        if c[i1] <= d[i2]:
            R[k] = c[i1]
            i1 += 1
        else:
            R[k] = d[i2]
            i2 += 1
        k += 1
    while i1 < n3:
        R[k] = c[i1]
        i1 += 1
        k += 1

    # Copy the remaining elements of R[], if there
    # are any
    while i2 < n4:
        R[k] = d[i2]
        i2 += 1
        k += 1


    i=0
    j=0
    k=l
    while i < Ln and j < Rn :
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    while i < Ln:
        A[k] = L[i]
        i += 1
        k += 1

    # Copy the remaining elements of R[], if there
    # are any
    while j < Rn:
        A[k] = R[j]
        j += 1
        k += 1

def mergeSort(A,low,high):
    if low < high:
        m1 = int((low+(high))/2)
        m2 = int((low+m1)/2)
        m3 = int(((m1+1)+high)/2)
        mergeSort(A, low, m2)
        mergeSort(A, m2+1, m1)
        mergeSort(A, m1+1, m3)
        mergeSort(A, m3+1, high)
        merge(A, low,m2, m1,m3, high)

print ("Enetr array size")
arr_size = int(input())
print ("Enetr array element")
A = [int(x) for x in input().split()]
mergeSort(A,0,arr_size-1)
print (" Your array after Sorting is")
for i in range(arr_size):
    print ("%d" %A[i]),

Screenshot of my editor

The Screenshot of Output Screen

Add a comment
Know the answer?
Add Answer to:
Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Consider a variation of Merge sort called 4-way Merge sort. Instead of splitting the array into...

    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) Give pseudocode for 4-way Merge sort. b) State a recurrence for the number of comparisons executed by 4-way Merge sort and solve to determine the asymptotic running time.

  • 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...

    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...

  • HW58.1. Array Merge Sort You've done merge (on Lists), so now it's time to do merge...

    HW58.1. Array Merge Sort You've done merge (on Lists), so now it's time to do merge sort (on arrays). Create a public non-final class named Mergesort that extends Merge. Implement a public static method int[] mergesort(int[] values) that returns the input array of ints sorted in ascending order. You will want this method to be recursive, with the base case being an array with zero or one value. If the passed array is null you should return null. If the...

  • This program should test the running time of these algorithms: Selection Sort Insertion Sort Bubble Sort...

    This program should test the running time of these algorithms: Selection Sort Insertion Sort Bubble Sort Merge Sort Quick Sort Heap Sort You have access to the implementation of all of these sorting algorithms, and you may use what is provided in your text directly. Be sure to cite the source of these implementations in the header of your program. Please maintain the property that these sorting algorithms sort arrays in ascending order. For this homework, you will write a...

  • Insertion sort on small arrays in merge sort Although merge-sort runs in Θ(n log n) worst-case...

    Insertion sort on small arrays in merge sort Although merge-sort runs in Θ(n log n) worst-case time and insertion sort runs in Θ(n 2 ) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of...

  • Please help me to solve the problem with java language! An implementation of the Merge Sort...

    Please help me to solve the problem with java language! An implementation of the Merge Sort algorithm. Modify the algorithm so that it splits the list into 3 sublists (instead of two). Each sublist should contain about n/3 items. The algorithm should sort each sublist recursively and merge the three sorted sublists. The traditional merge sort algorithm has an average and worst-case performance of O(n log2 n). What is the performance of the 3-way Merge Sort algorithm? Merge Sort algorithm...

  • Modify the sorts (selection sort, insertion sort, bubble sort, quick sort, and merge sort) by adding code to each to tally the total number of comparisons and total execution time of each algorithm. E...

    Modify the sorts (selection sort, insertion sort, bubble sort, quick sort, and merge sort) by adding code to each to tally the total number of comparisons and total execution time of each algorithm. Execute the sort algorithms against the same list, recording information for the total number of comparisons and total execution time for each algorithm. Try several different lists, including at least one that is already in sorted order. ---------------------------------------------------------------------------------------------------------------- /** * Sorting demonstrates sorting and searching on an...

  • 6 6. Merge Bubble Sort: a) How does the merge bubble sort break the array into...

    6 6. Merge Bubble Sort: a) How does the merge bubble sort break the array into sublists? b) What does it need to use for each sublist and then what does it do with all of the sublists? c) What is the Big-O notation for this sort? 7. Merge Sort: a) How does the merge sort use recursion to break the array into sublists? b) What happens to each of these sublists to get the final sorted list? c) What...

  • In this assignment you will implement merge-sort algorithm by creating 2 threads instead of 2 pro...

    In this assignment you will implement merge-sort algorithm by creating 2 threads instead of 2 processes. First half of the array will be sorted by thread 1 and the second half by thread 2. When the threads complete their tasks, the main program will merge the half arrays. You should not waste your time on merge-sort algorithm. Use the merge sort algorithm given below Languaga is C platform Ubuntu

  • Please come up with an array of 9 random integers then sort the array. Show the...

    Please come up with an array of 9 random integers then sort the array. Show the contents of the array each time a sorting algorithm changes it while sorting the array into ascending order. The 6 sorting algorithm we are using are: 1. Selection Sort 3 points 2. Insertion Sort 3 points 3. Shell Sort 6 points 4. Bubble Sort 3 points 5. Merge Sort 10 points 6. Quick Sort 10 points It is OK to do this assignment on...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
Active Questions
ADVERTISEMENT