In: Computer Science
(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
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
lognlogn 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 lognlogn splits,
each of which costs nn for a total of nlognnlogn operations. A
merge sort is an O(nlogn)O(nlogn) 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(nlogn) 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.