Q1. (a) Suppose that a binary search is made through an ordered list L, of lengt
ID: 3713554 • Letter: Q
Question
Q1. (a) Suppose that a binary search is made through an ordered list L, of length 20, for an item X, which tlyi e .leanyae ale i. in the best case scenario? ii. in the worst case scenario? iii. in the average case scenario (for this part- your answer might not be an integer)? [11 marks] (b) Write down the intermediate words that are constructed after each iteration when the letters in the word "gdansk" are alphabetically ordered using i. bubble sort 11. quicksort 12 marks] (c) Calculate the computational complexity (in "Big Oh" notation) of the bubblesort algo- rithm. [10 marksExplanation / Answer
1.a) i)The best case scenario , the element X is found at the middle of the list, i.e. at position 10 and there is only one comparison
ii)In the worst case scenario, the item is not found in the list. It is either smaller than all the elements in the list or is larger than all the elements in the list. Now, at each step, we make a comparison and divide a list of n elements into a list of (n-1)/2 elements. We continue doing this untill there is only one element left. Thus there will be log2(n-1) comparisons in this case i.e. log2(20-1) = 5(rounding up) comparisons.
iii)let the array have positions 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20. The element st 10 th position requires 1 comparison. element at position 5,15 in 2nd comparison. Elements at position 2,7,12,18 at 3rd comparison.Elements at position 1,3,6,8,11,13,16,19 at 4th comparison and the elements at position 4,9,14,17,20 at the 5th comparison. Thus average comparisons = (1x1 + 2x2 + 4x3 + 8x4 + 5x5)/20 = 3.7
1.b) i. The intermediate words for bubble sort are:
ii) The intermediate words for quick sort are:
1.c) Bubble Sort is a sorting algorithm that repeatedly swaps the adjacent elements if they are in wrong order. Now, for an array of n elements, in the first iteration, it looks at n elements and puts the largest element at n-1th position. Then it looks at n-1 elements at puts the second largest at n-2th position. Then it looks at n-2 elements and puts the third largest at n-3th position and it goes on . So, total comparisons = n+ n-1 + n-2 + ....... + 2 + 1 = n(n+1)/2 = O(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.