Question

In: Computer Science

(a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted...

(a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Mergesort. Count the number of comparisonsmade.

(b) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Heapsort

Solutions

Expert Solution

Merge sort is a recursive algorithm that continually divide a list in half. If the list is vacant or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list. .

The mergeSort function shown begins by asking the base case question. If the length of the list is less than or equal to one, then we already have a sorted list and no more processing is necessary. On the contrary if the length is greater than one, then we use the Python slice operation to extract the left and right halves. It is important to note that the list may not have an even number of items. That does not matter, as the lengths will differ by at most one.

Step 1---5, 13, 2, 25, 7, 17, 20, 8, 4 splits into two halves 5,13,2,25 and 7,17,20,8,4

step 2----5,13,2,25 again splitted into 5,13 and 2,25 second half splitted into 7,17 and 20,8,4

step 3---again 5 and 13 and 2,25 are splitted and here 7,17 are splitted and 20 is splitted 8, 4

step 4-- In this step 8 and 4 are splitted

step5---Merge is applied and a new sorted lis2,25 and 5,13 and7,17 and 4,8,20 is obtained

step6-- Again Merging finally sort the numbers as2, 5,7,8,,13,17,20,25

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] <= righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [5, 13, 2, 25, 7, 17, 20, 8, 4 ]
mergeSort(alist)
print(alist)
The output will be like this:

Splitting  [5, 13, 2, 25, 7, 17, 20, 8, 4]
Splitting  [5, 13, 2, 25]
Splitting  [5, 13]
Splitting  [5]
Merging  [5]
Splitting  [13]
Merging  [13]
Merging  [5, 13]
Splitting  [2, 25]
Splitting  [2]
Merging  [2]
Splitting  [25]
Merging  [25]
Merging  [2, 25]
Merging  [2, 5, 13, 25]
Splitting  [7, 17, 20, 8, 4]
Splitting  [7, 17]
Splitting  [7]
Merging  [7]
Splitting  [17]
Merging  [17]
Merging  [7, 17]
Splitting  [20, 8, 4]
Splitting  [20]
Merging  [20]
Splitting  [8, 4]
Splitting  [8]
Merging  [8]
Splitting  [4]
Merging  [4]
Merging  [4, 8]
Merging  [4, 8, 20]
Merging  [4, 7, 8, 17, 20]
Merging  [2, 4, 5, 7, 8, 13, 17, 20, 25]
[2, 4, 5, 7, 8, 13, 17, 20, 25]

In order to analyze the mergeSort function, we need to consider the two distinct processes that make up its implementation. First, the list is split into halves. We already computed (in a binary search) that we can divide a list in half lognlog⁡n times where n is the length of the list. The second process is the merge. Each item in the list will eventually be processed and placed on the sorted list. So the merge operation which results in a list of size n requires n operations. The result of this analysis is that lognlog⁡n splits, each of which costs nn for a total of nlognnlog⁡n operations. A merge sort is an O(nlogn)O(nlog⁡n) algorithm.

Recall that the slicing operator is O(k)O(k) where k is the size of the slice. In order to guarantee that mergeSort will be O(nlogn)O(nlog⁡n) we will need to remove the slice operator. Again, this is possible if we simply pass the starting and ending indices along with the list when we make the recursive call. We leave this as an exercise.

It is important to notice that the mergeSort function requires extra space to hold the two halves as they are extracted with the slicing operations. This additional space can be a critical factor if the list is large and can make this sort problematic when working on large data sets

b)Max Heap Sort Steps:

1. Max-heapify the tree

. 2. Replace the root with the last element , and place the last element aside.

3. Put the last element in the last empty node.


Related Solutions

(a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted...
(a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Mergesort. Count the number of comparisons made. (b) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Heapsort.
Problem 1 (4+3 marks). (a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20,...
Problem 1 (4+3 marks). (a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Mergesort. Count the number of comparisons made. (b) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Heapsort.
Data: 7,-5, -8, 7, 9, 15, 0, 2, 13, 8, 6, -2, 4 (a) Mean= Mode=...
Data: 7,-5, -8, 7, 9, 15, 0, 2, 13, 8, 6, -2, 4 (a) Mean= Mode= median= (b) Variance= Standard deviation= (c) Range= IQR(Interquartilerange)= (d) Mid-Range= Mid-Hinge=
5.) For the data set 2 4 4 5 7 8 9 10 12 12 13...
5.) For the data set 2 4 4 5 7 8 9 10 12 12 13 13 16 16 16 16 17 19 19 20 23 24 24 24 25 26 26 27 28 28 29 31 32 34 34 36 37 38 42 44 45 46 47 47 48 50 52 53 53 54 55 56 56 57 58 (a) Find the 80th percentile. The 80t percentile is =    (a) Find the 42nd percentile. The 42nd percentile is...
A=[ 7 8 -2 -6 7 4 1 ; 2 4 -4 -13 9 9 -12...
A=[ 7 8 -2 -6 7 4 1 ; 2 4 -4 -13 9 9 -12 ; 6 6 0 -9 8 9 -4 ; 1 8 -14 -22 5 8 -1 ; 4 9 -10 -14 7 4 -1] B=[ 19 4 4 14 -3 -7 -5 ; 21 -6 -5 10 14 -2 4 ; 22 -4 5 13 5 -6 4 ; 41 20 0 26 11 -1 -27 ; 29 14 -2 20 3 -4 -19]...
A = [4, 5, 9] B = [-4, 5, -7] C = [2, -7, -8, 5]...
A = [4, 5, 9] B = [-4, 5, -7] C = [2, -7, -8, 5] D = [1, -9, 5, -3] E = [3, 3, -1] Uz = 1/|z| ^z d(X,Y) = (Rθ) d = diameter R = Radius θ = Theta Find a. Uc b. d (D, C) c. Let P = B + 3E, UP = d. A x B e. 3B x E f. C x D
Using the following data set: 10, 5, 2, 7, 20, 3, 13, 15, 8, 9 Apply...
Using the following data set: 10, 5, 2, 7, 20, 3, 13, 15, 8, 9 Apply the Merge sort algorithm. [Show to sorting process of the first half only] Apply the Quick sort algorithm [Show the first partitioning implementation]
Q4: . The sorted values array contains the sixteen integers 1, 2, 3, 13, 13, 20,...
Q4: . The sorted values array contains the sixteen integers 1, 2, 3, 13, 13, 20, 24, 25, 30, 32, 40, 45, 50, 52, 57, 60. How many recursive calls are made by our binarySearch method given an initial invocation of binarySearch(45, 0, 15)? Answer Choices : 2     0     3     4     1
Match No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14...
Match No. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Player A 8 42 56 68 91 123 12 46 57 137 5 80 14 10 19 Player B 38 44 46 59 57 61 48 42 51 39 58 41 55 45 68 1. For the given data set representing the runs scored by two players in last 15 matches, conduct the following analysis: i. Which average you will use to summarize...
A = (1 −7 5 0 0 10 8 2 2 4 10 3 −4 8...
A = (1 −7 5 0 0 10 8 2 2 4 10 3 −4 8 −9 6) (1) Count the number of rows that contain negative components. (2) Obtain the inverse of A and count the number of columns that contain even number of positive components. (3) Assign column names (a,b,c,d) to the columns of A. (4) Transform the matrix A into a vector object a by stacking rows. (5) Replace the diagonal components of A with (0,0,2,3). Hint:...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT