ASSIGNMENT-2(GRADED) if right-left <= 0 return else pivot = A[right] partition =
ID: 3874047 • Letter: A
Question
ASSIGNMENT-2(GRADED)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure
USING THE ABOVE PSEUDO CODE SORT THE FOLLOWING ARRAY
99,32,27,48,72,3,100
2. WHAT IS THE DIFFRENECE BETWEEN MERGE AND INSERTION SORT?EXPLAIN WITH AN ARRAY?
3. WHAT IS VALUE OF LOG(300)?
4.EXPLAIN THE DIFFERENCE BETWEEN BFS AND DFS WITH DIAGRAM?
Explanation / Answer
1. The steps are as follows:
99,32,27,48,72,3,100
Procedure calls where (right-left) > 0 are shown in the steps:
Step 1 - partition around 100 (left = 0 , right = 6)
99,32,27,48,72,3,100 (partition = 6)
Step 2 - partition around 3 (left = 0 , right = 5)
3,99,32,27,48,72,100 (partition = 0)
Step 3 - partition around 72 (left = 1 , right = 5)
3,32,27,48,72,99,100 (partition = 4)
Step 4 - partition around 48 (left = 1 , right = 3)
3,27,32,48,72,99,100 (partition = 3)
Step 5 - partition around 32 (left = 1 , right = 2)
3,27,32,48,72,99,100 (partition = 2)
Step 6 - partition around 27 (left = 1 , right = 1)
The resultant array is
3,27,32,48,72,99,100
2. Difference between mergesort and insertion sort
Let the given array as
99,32,27,48,72,3,100
In the case of insertion sort, we loop from i = 1 to n
we pick array[i] and insert it in sorted array[0..i-1]
So the given example we have:
99,32,27,48,72,3,100
picking 32 (i=1) and inerting at right position in array[0..1] we get
32,99,27,48,72,3,100
picking 27(i=2) and inerting at right position in array[0..2] we get
27,32,99,48,72,3,100
picking 48 (i=3) and inerting at right position array[0..3]we get
27,32,48,99,72,3,100
picking 72 (i=4) and inerting at right position we get array[0..4]
27,32,48,72,99,3,100
picking 3 (i=5) and inerting at right position we get array[0..5]
3,27,32,48,72,99,100
picking 100 (i=6) and inerting at right position we get array[0..6]
3,27,32,48,72,99,100
The sorted array is :
3,27,32,48,72,99,100
In case of mergesort we divide the array into almost equal halves till we get a single element in the sublist. Then we merge the sublists as per sorted order till we get a single list. The steps are as follows:
99,32,27,48,72,3,100
99,32,27 48,72,3,100
99,32 27 48,72 3,100
99 32 27 48 72 3 100
32,99 27 48,72 3,100
27,32,99 3,48,72,100
3,27,32,48,72,99,100
3. Value of log(300) to the base 10 = 2.477121
4. Difference between BFS (Breadth First Search) and DFS (Depth First Search) is as follows:
Given a tree
1
/
2 3
/ /
4 5 6 7
A Depth First Search means we will first search the depth for each node ( we will travel upto the leaf node and then backtrak). It closely resembles the preorder traversal of the tree. Left edge is prefered over the right edge while traversing.
So the order as per DFS will be : 1 2 4 5 3 6 7
A BFS or breadth first search is like a level search, in this first all the child of the node are visited then the next level nodes are considered.
So the order as per BFS will be as follows: 1 2 3 4 5 6 7