s2004- Data Structures and Algorithms OMS2004-2017 ) Linked Lists Tutorial 5 Con
ID: 2247129 • Letter: S
Question
s2004- Data Structures and Algorithms OMS2004-2017 ) Linked Lists Tutorial 5 Consider the following algorithm: void Algorithm (intall, int size)( e arswer ut of 10.00 queston 1. int value; 2. int q 3, for (int p = 1; p value 66 q >= )( value- alpl; q = p-1; q-1; 8. 9. 10, q = a[q+1] = value ; 12.) (a) What do you think is the purpose of the algorithm? Copy the first element across the array (b) What is the Big-O notation for the worst-case caoran array from fargest to smallest an array fron all-st to largest O(n) o(n!) are given the following array, a (56,81.4.7.30, if we print the array between lines 3 and 4, w output at the tollowing iterations of the for-loop. Given you answer in the same format as the array above. eg SAMSUNGExplanation / Answer
a)The purpose of the algorithm is to sort an array from smallest to largest.
Take the size of an array 5 .suppose i take 15,20,12,10,30
In the 1st iteration value=20,q=1-1--->q=0
in while loop a[q] means a[0] =15>20&&0>=0 as the 1st condition is false ...
the loop will be exit and 15 will be stored in a[q+1] i.e., a[0]
likewise ,all the elements will be tested and the array contains 10,12,15,20,30
b)consider array size is 5 and the array elements 5,4,3,2,1 which are in descending order
for each element to get sorted it takes 5 iterations which is equal to the size of an array
so for one element 5 iterations then for all the iterations 5*5
hence for the worst case complexity it is O(n2)
c)the first iteration of the for loop will be same as the array elements because 56<81-->56,81,30,4,7
the second iteration of the loop is 4,56,81,7,30
the third iteration of the loop is 4,7,56,81,30
the fourth iteration of the loop is 4,7,30,56,81
the final iteration is 4,7,30,56,81
d)In the line 6:if the symbol < is relplaced with > then the elements will be inverted as the
largest element will be stored in the first place
e) (9,8,7,6,5,4,3,2,1) will result in the worst case algorithm complexity
as all the elements are to be sorted and the complexity will be O(n2) as discussed above
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.